CodeChef March Long Challenge Solution | College Life 4 solution in Java | AskTheCode
Problem:
Chef and N−1 more of his friends go to the night canteen. The canteen serves only three items (well, they serve more, but only these three are edible!), which are omelette, chocolate milkshake, and chocolate cake. Their prices are A, B and C
respectively.
However, the canteen is about to run out of some ingredients. In particular, they only have E
eggs and H chocolate bars left. They need:
2 eggs to make an omelette
3 chocolate bars for a chocolate milkshake
1 egg and 1 chocolate bar for a chocolate cake
Each of the N friends wants to order one item. They can only place an order if the canteen has enough ingredients to prepare all the ordered items. Find the smallest possible total price they have to pay or determine that it is impossible to prepare N items.
Input:
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains six space-separated integers N, E, H, A, B and C.
Output:
For each test case, print a single line containing one integer ― the minimum cost of N items, or −1 if it is impossible to prepare N items.
Example Input:
3 5 4 4 2 2 2 4 5 5 1 2 3 4 5 5 3 2 1
Example Output:
-1 7 4
Explanation:
Example case 1: The maximum number of items that can be produced using 4 eggs and 4 chocolates is 4, so the answer is −1.
Example case 2: In the optimal solution, the friends should order 2
omelettes, 1 chocolate milkshake and 1 chocolate cake, with cost 1⋅2+2⋅1+3⋅1=7.
Example case 3: In the optimal solution, the friends should order 4 chocolate cakes, with cost 1⋅4=4.
Code:
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 long solve(long n, long e, long h, long a, long b, long c){
//long ans = Integer.MAX_VALUE;
long ans = (long)1e15;
if(n<=0){
return 0;
}
if(n<=e && n<=h){
ans = Math.min(ans,n*c);
}
if(2*n <= e){
ans = Math.min(ans,n*a);
}
if(3*n <= h ){
ans = Math.min(ans, n*b);
}
if((h-n)/2 >= 1 && (h-n)/2 >= n-e){
if(b-c<0){
long x = Math.min(n-1,(h-n)/2);
ans = Math.min(ans,(b-c)*x+n*c);
}
else{
long x = Math.max(1,(n-e));
ans = Math.min(ans,(b-c)*x+n*c);
}
}
if((e-n)>=1 && (e-n)>=n-h){
if(a-c<0){
long x = Math.min(n-1,(e-n));
ans = Math.min(ans,(a-c)*x+n*c);
}
else{
long x = Math.max(1,(n-h));
ans = Math.min(ans,(a-c)*x+n*c);
}
}
if(e/2 >= 1 && e/2>=(3*n-h+2)/3){
if(a-b<0){
long x = Math.min(n-1,(e/2));
ans = Math.min(ans,(a-b)*x+n*b);
}
else{
long x = Math.max(1,((3*n-h+2)/3));
ans = Math.min(ans,(a-b)*x+n*b);
}
}
if(e>=3 && h>=4 && n>=3){
ans = Math.min(ans,a+b+c+solve(n-3,e-3,h-4,a,b,c));
}
return ans;
}
public static void main (String[] args) throws java.lang.Exception{
Scanner s = new Scanner(System.in);
int t = s.nextInt();
while(t-->0){
long n = s.nextLong();
long e = s.nextLong();
long h = s.nextLong();
long a = s.nextLong();
long b = s.nextLong();
long c = s.nextLong();
long result = solve(n,e,h,a,b,c);
if(result == (long)1e15){
System.out.println("-1");
}
else{
System.out.println(result);
}
}
}
}
Comments