Header Ads Widget

Chef and Magical Jars | codechef solution

Rajnish Tripathi 15:03

Problem:- 

Chef decided to teach some advanced recipes to junior chefs. On the very first day of their cooking sessions, to identify the cooking abilities of each junior chef, Chef instructed them to make their premier dishes. The junior chefs were very excited and they all went into the kitchen to cook their dishes.

Chef has a limited number of jars in the kitchen. The jars are magical ― if a chef that is cooking a dish requiring � ingredients takes � jars, each of these jars fills itself with one of the required ingredients, and after this chef finishes cooking and returns the jars to the kitchen, they empty themselves (and are ready for other chefs to take some or all of them). Of course, this means it is impossible to cook a dish requiring � ingredients with less than � jars.

Since Chef did not tell the junior chefs in which order they should prepare their dishes, they started picking up jars simultaneously and in the end, no junior chef was able to acquire enough jars to prepare their premier dish. Also, none of the junior chefs are willing to lend their jars to others. Chef was unable to handle the situation and decided to call off the cooking session for that day, so that he could get more jars and try it again later.

You know that there are � junior chefs (numbered 1 through �) and for each valid �, the number of ingredients required for the dish of the �-th chef is ��. If there are � jars, then formally, the following process happens:

  • The junior chefs take some jars; let's denote the number of jars taken by the �-th chef by ��. Any distribution of jars such that 0≤�� for each valid � and ∑�=1���=� is possible.
  • At any time, if ��<�� for each chef � that has not prepared their dish yet, the cooking session is a failure.
  • Otherwise, one of the chefs who have at least as many jars as the number of required ingredients prepares their dish and returns their jars to the kitchen.
  • Whenever some jars are returned to the kitchen, they are immediately taken by some chefs that have not prepared their dishes yet (possibly all the jars by one chef).
  • This process continues with chefs taking jars, cooking their dishes and returning jars, until no chef can cook their dish anymore or all chefs have cooked their dishes.
  • When all junior chefs have successfully cooked their dishes, the cooking session ends successfully.

Chef wants to know the minimum number of magical jars that should be present in the kitchen initially so that the session would be successful regardless of how the junior chefs pick up the jars. Chef is a legendary cook, but he is not very good at mathematics, so he asks you to find that number.

Input

  • The first line of the input contains a single integer � denoting the number of test cases. The description of � test cases follows.
  • The first line of each test case contains a single integer �.
  • The second line contains � space-separated integers �1,�2,…,��.

Output

For each test case, print a single line containing one integer ― the minimum required number of jars.

Constraints

  • 1≤�≤1,000
  • 1≤�≤105
  • 1≤��≤109 for each valid �
  • the sum of � over all test cases does not exceed 106

Subtasks

Subtask #1 (100 points): original constraints

Sample 1:

Input
Output
2   
4   
1 1 1 1   
2   
1 4
1   
4

Explanation:

Example case 1: One of the junior chefs always picks up the only jar, cooks their dish and returns the jar back to the kitchen. Then, another junior chef picks up that jar, cooks their dish and returns the jar. This procedure can be repeated by each junior chef so that they can cook their recipe.

code(c++):-

#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
long long n;
cin>>n;
long long ans = 0;
for(long long i=0;i<n;i++){
long long a;
cin>>a;
ans = ans + (a-1);
}
cout<<(ans+1)<<endl;
}
    // your code goes here
    return 0;
}


Code(JAVA):-

import java.util.*;
class Codechef{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
long n=sc.nextLong();
long m=0;
for(int i=0;i<n;i++){
long s=sc.nextLong();
m+=s;
}
System.out.println(m-n+1);
}
}
}


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