Chef and Stones Codechef Solution

Hello Programmers In this post, you will know how to solve the Chef and Stones Codechef Solution.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

report this adProblem

Chef is playing a game. Currently in the game, he is at a field full of stones. There are total N kinds of stones. There is unlimited supply of each kind of stone.

Chef knows that one stone of kind i needs A_i minutes to pick it from the ground and it will give Chef a profit of B_i Rs.

Chef has K minutes of free time. During this free time, Chef want to pick stones so as to maximize his profit. But he can not pick stones of different kinds, he has to pick stones of a single kind.

Please help Chef to find the maximal possible profit.

Input

• First line contains single integer T denoting the number of test cases.
• First line of each test case contains two integers N and K.
• Next line contains N integers A_i denoting the time needed to pick one stone of kind i.
• Next line contains N integers B_i denoting the profit due to picking i^thth stone.

Output

• For each test case, print a single line containing maximal possible profit.

Constraints

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 10⁹
• 1 ≤ A_i, B_i ≤ 10⁹

Subtasks

• Subtask N ≤ 5, T ≤ 2 Points: 30
• Subtask N ≤ 10⁵, T ≤ 5 Points: 70

Example

Input:
1
3 10
3 4 5
4 4 5
Output:
12

Explanation

If Chef picks stones of first kind he can pick 3 stones, he will get a profit of 3*4 = 12 Rs.
If Chef picks stones of second kind he can pick 2 stones, he will get a profit of 2*4 = 8 Rs.
If Chef picks stones of third kind he can pick 2 stones, he will get a profit of 2*5 = 10 Rs.

So the maximum possible profit is 12

Chef and Stones CodeChef Solution in JAVA

import java.util.*;
class Chef_and_Stones {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        while (t-- > 0) {
            int n = input.nextInt();
            long k = input.nextLong();
            long arr1[] = new long[n];
            long arr2[] = new long[n];
            for (int i = 0; i < n; i++) {
                arr1[i] = input.nextLong();
            }
            for (int i = 0; i < n; i++) {
                arr2[i] = input.nextLong();
            }
            long ans = Long.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                long temp = arr1[i];
                long cost = 0;
                long count = 1;
                while ((temp * count) <= k) {
                    cost = arr2[i] * count;
                    count++;
                }
                ans = Math.max(ans, cost);
            }
            System.out.println(ans);
        }
        input.close();
    }
}

Chef and Stones CodeChef Solution in CPP

#include <bits/stdc++.h>
using namespace std;
int main() {
	// your code goes
	int t;
	cin>>t;
	while(t--){
	    long long int n,k;
	    cin>>n>>k;
	    long long int a[n];
	    long long int b[n];
	    long long int maxi=INT_MIN;
	    for(int i=0;i<n;i++){
	        cin>>a[i];
	    }
	    for(int i=0;i<n;i++){
	        cin>>b[i];
	    }
	    long long int pro;
	    for(int i=0;i<n;i++){
	        pro=k/a[i];
	        maxi=max(maxi,pro*b[i]);
	    }
	    cout<<maxi<<endl;
	}
	return 0;
}

Chef and Stones CodeChef Solution in Python

for _ in range(int(input())):
    n, k = map(int, input().split())
    time = list(map(int, input().split()))
    profit = list(map(int, input().split()))
    maxi = 0
    for i in range(n):
        temp = (k//time[i])*profit[i]
        if temp > maxi:
            maxi = temp
    print(maxi)

report this ad

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

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Chef Chick Codechef Solution