After the season of online classes, now it’s time for evaluation. A teacher wants to evaluate the students by giving them assignments. The teacher thinks that the best way to evaluate the students is to make them present on some topics in front of the whole class. So, he has asked you to choose the topics on which each student will present.
For convenience, the teacher has given you a list of probable topics from each chapter. But, he also gave you some conditions while choosing these topics:
As Fafa is the class representative, the teacher has asked him to provide a list of topics that each student chooses.
Now, the problem is no student wants to choose more than one topic but in that case, a lot of topics remain unassigned. Then the teacher will become very angry. Fafa and others don't want to face this situation. So they have decided that each student will choose an equal number of topics. Also, to avoid any clash, the students have agreed to assign the topics randomly satisfying all the rules stated by the teacher.
Now, Fafa is busy with writing a program that will randomly assign exact topics to each student. He has asked your help to find the optimal number that denotes the number of topics that will be assigned to each student. In other words, he asked you to find the maximum number of topic each student will choose so that the number of topics that are not chosen is as minimum as possible. It is guaranteed that each student will get at least one topic.
The first line of the input will contain a single integer that denotes the number of test cases.
For each test case, the first line will contain integers and where denotes the number of chapters and denotes the number of students in your class.
Next line will contain space-separated integers where denotes the number of topics from chapter. Here, will always be greater than or equal to the number of students.
For each case, print the case number and the maximum number of topics that can be assigned to each student satisfying all conditions.
3 3 8 2 5 1 4 2 4 3 2 1 1 4 8
Case 1: 1 Case 2: 3 Case 3: 2
For first test case, each student can take maximum 1 topics and there won't be any topic left
For second test case, each student can take maximum 3 topics, one will take 3 topics from chapter 1 and another student will take 3 topics from chapter 2. Total 4 topics will be left.
For third test case, 4 students each takes 2 topics and no topics will be left.
Login to submit
An efficient solution will be to run a binary search on output. We will run binary search on how man...