Header Ads Widget

Buying Sweets | codechef solultion

Rajnish Tripathi 05:30

Problem

There are � sweets in the store. The cost of the ��ℎ sweet is �� rupees. Chef is a regular customer, so after buying the ��ℎ sweet, he gets a cashback of �� rupees.

Chef has � rupees. He is fond of all the sweets, so he wants you to calculate the maximum number of sweets he can buy. Note that he can buy the same type of sweet multiple times, as long as he has the money to do so.

Input Format

  • The first line of input will contain �, the number of test cases.
  • Each test case consists of three lines of input.
  • The first line of each test case contains two space-separated integers � and � — the number of sweets in the shop and the amount of money Chef has.
  • The second line of each test case contains � space-separated integers �1,�2,…,��.
  • The third line of each test case contains � space-separated integers �1,�2,…,��.

Output Format

For each query, print on a new line the maximum number of sweets Chef can buy.

Constraints

  • 1≤�≤2⋅105
  • 1≤�≤2⋅105
  • 1≤��<��≤109
  • 1≤�≤109
  • It is guaranteed that the sum of � over all test cases does not exceed 2⋅105

Sample 1:

Input
Output
3
3 3
2 3 4
1 1 1
2 4
5 4
1 2
4 10
4 4 5 5
1 2 4 2
2
1
7

Explanation:

Test case 1: Chef buys the first sweet, which costs 2 rupees and has a cashback of 1 rupee. He now has 3−2+1=2 rupees remaining. He once again buys the first sweet, which leaves him with 1 rupee, at which point no more sweets can be bought.

Test case 2: Chef buys the second sweet once.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;

void solve () {
int n, r, a, b;
vector<int> as, bs;
cin >> n >> r;
for (int i = 0; i < n; i++) {
cin >> a;
as.push_back(a);
}
for (int i = 0; i < n; i++) {
cin >> b;
bs.push_back(b);
}
vector<pair<int, int>> sweets(n);
for (int i = 0; i < n; i++) {
sweets[i] = {as[i] - bs[i], as[i]};
}
sort(sweets.begin(), sweets.end());
int count = 0;
for (auto elem : sweets) {
int diff, price;
tie(diff, price) = elem;

if (r >= price) {
int num_sweets = (r-price) / diff + 1;
r -= diff * num_sweets;
count += num_sweets;
}
}
cout << count << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
     solve();
    return 0;
}

Code(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
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(br.readLine()),n,k,x,y;
        while(t-->0)
        {
         String s1[]=br.readLine().split(" "),s[]=br.readLine().split(" ");
         n=Integer.parseInt(s1[0]);k=Integer.parseInt(s1[1]);
         s1=br.readLine().split(" ");
         int a[][]=new int[n][2];
         for(int i=0;i<n;i++)
         {
         y=Integer.parseInt(s[i]);
         x=y-Integer.parseInt(s1[i]);
         a[i][0]=x;
         a[i][1]=y;
         }
         Arrays.sort(a,new Comparator<int[]>(){
         public int compare(final int a[],final int b[]){
         if(a[0]>b[0])
         return 1;
         else if(a[0]==b[0]&&a[1]>b[1])
         return 1;
         return -1;
         }
         });
         x=0;
         for(int i=0;i<n;i++)
         {
         if(k<1)
         break;
         if(a[i][1]>k)
         continue;
         y=(k-a[i][1])/a[i][0]+1;
         x+=y;
         k-=y*a[i][0];
         }
         System.out.println(x);
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags:

Post a Comment

0 Comments