Buying Sweets Codechef Solution

Buying Sweets Codechef Solution: Banknotes in the state of Strangeland don’t have any regulated values like 1, 5, 10, 20, 50, 100, etc. In fact, it’s possible to see any positive integer on a banknote of Strangeland. Indeed, this isn’t the most convenient thing.

Ann is working as a sweet seller at a shop in Strangeland. Every kind of sweets in this shop has its own cost, and sweets of the same kind have the same cost.

Customers in Strangeland are strange. A customer points at some kind of sweets and gives several banknotes to the seller. This means that he wants to buy a positive number of sweets of that kind. He doesn’t tell the exact number of sweets he wants to buy. The only thing Ann knows is: an ‘adequate’ customer won’t give any extra banknotes. It means that if you throw away any banknote, the resulting amount of money won’t be enough to buy the wanted number of sweets.

Ann has to determine the number of sweets the customer wants. Help Ann write a program which determines this number or tells that it’s impossible.

Input

The first line of the input contains a single integer T, the number of test cases (no more than 20). T test cases follow. Each test case consists of two lines. The first of these lines contains two integers N and X (1 ≤ NX ≤ 100) separated by a single space. N is the number of banknotes given by the customer. X is the cost of a single sweet of the chosen kind. The second of these lines contains N space-separated integers Ai (1 ≤ Ai ≤ 100), the values of the banknotes.

Output

For each test case output exactly one line containing a single integer:

  • -1 if the customer is inadequate and has given extra banknotes, or
  • K, the number of sweets the customer wants to buy. If there are several possible answers, output the largest of them.

Example

Input:
3
4 7
10 4 8 5
1 10
12
2 10
20 50
Output:
-1
1
7

Explanation

In the first test case, the total amount of money received from the customer is 27. He can’t buy more than 3 sweets with this amount. If you throw away the banknote of value 5 (or of value 4), it will still be possible to buy 3 sweets. Hence the customer is inadequate.

In the second test case, it’s clear that he wants to buy just one sweet (note that this number should be positive).

In the third test case, the total amount of money received is 70, which is enough for 7 sweets. The customer might want to buy only 6 sweets, but we are interested in the largest possible answe

Buying Sweets – CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i = 0 ; i < t; i++)
		{
		    int N = sc.nextInt();
		    int X = sc.nextInt();
		    int sum = 0 , min = Integer.MAX_VALUE;
		    for(int j = 0 ; j < N; j++)
		    {
		        int val = sc.nextInt();
		        sum += val;
                if(min > val)
                    min = val;
		    }
		    if((sum % X == 0) || (min > (sum % X)) )
		    {
		        System.out.println(sum/X);
		    }
		    else
		    {
		       System.out.println(-1);
		    }
		}
	}
}

Buying Sweets – CodeChef Solution in CPP

#include<bits/stdc++.h>
using namespace std;
#define tr(c,it) for(typeof(c.begin()) it=c.begin();it!=c.end();++it)
#define all(c) c.begin(),c.end()
#define mod 1000000007
#define itor(c) typeof(c.begin())
// #define ll long long
#define vi vector<int>
#define si set<int>
#define msi multiset<int>
#define ii pair<int,int>
#define sii set<ii>
#define vii vector<ii>
#define vvi vector<vi>
#define pb push_back
#define mp make_pair
#define vll vector<ll>
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"
#define fast ios_base::sync_with_stdio(false); cin.tie(0);
#define fo(i,s,e) for(long long int i=s;i<=e;i++)
#define ff first
#define ss second
#define tc ll t;cin>>t; while(t--)
#define forin(v,x,n) fo(i,0,n-1){cin>>x;v.pb(x);}
#define printv(v) for(auto i:v){cout<<i<<" ";} cout<<"\n";
#define full(v) v.begin(),v.end()
int gcd(int a, int b)
{
    while (true)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
}
int lcm(int a, int b)
{
    int temp = gcd(a, b);
    return temp ? (a / temp * b) : 0;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
bool cmp(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}
int main(){
 #ifndef ONLINE_JUDGE
    freopen("input1.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#endif
#ifndef ONLINE_JUDGE
    freopen("Error.txt","w",stderr);
#endif
 fast
 tc{
        ll n,x;
        cin>>n>>x;
        vector<ll>v(n);
        ll ans=0;
        ll sum=0;
        for(ll i=0;i<n;i++)
        {
            cin>>v[i];
            // sum+=v[i];
        }
        for(ll i=0;i<n;i++)
        {
           sum+=v[i];
        }
        ll r=sum%x;
        debug(r);
        sort(v.begin(), v.end());
        if(v[0]<=r){
            cout<<-1<<endl;
        }
        else
        {
            cout<<sum/x<<endl;
        }
    }
return 0;
}

Disclaimer: The above Problem (Buying Sweets) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment