Description
Little brick is once playing a RPG game.
In this game, there are some magical reels(魔法卷軸) that can increase your skill level.
As a serious OCD patient (強迫症患者),
he can only accept that every skill he has is at the same level.
At the beginning, every skill is at level 0,
and he has N magical reels,
the ith reel can increase one of his skill by Xi levels.
LittleBrick wants to have as many skills as possible,
and he also want to use all N reels.
Tell LittleBrick what is the maximum number of skills he may have.
ouo.
For Example 1:
6
1 1 2 2 3 3
The answer is 4, since you can make 4 skills to reach the same level 3,
by distributing the reels like (1, 2), (3), (1, 2), (3)
For Example 2:
5
1 1 2 5 3
The answer is 2, since you can make 2 skills to reach the same level 6,
by distributing the reels like (1, 5), (1, 2, 3)
For Example 3:
3
1 2 4
The answer is 1, since you can make only 1 skill to reach the same level 7,
by distributing the reels like (1, 2, 4)
HINTS :
1. You can get testcases 1 ~ 3 by using the same code that you used in your final practice "The Beauty of Distributing".
2. In order to get testcases 4 ~ 6, we suggest you to do some optimizations (優化).
MORE HINTS :
1. We suggest you to do "3 optimizations" in your code.
2. We give you a piece of sample code below for your reference, and use it to further explain the three optimizations:
I. We've provided Optimization 3 in the sample code below for you to use directly.
II. We've also highlighted the recommended places for Optimization 1 and Optimization 2 in the sample code.
Sample code:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
int n, box; // n = total reel number, box = SUM / ans
int a[1000];
bool vis[1000];
bool solver(int step, int sum) {
if (step == n) return true;
for (int i = 0; i < n; i++) {
// Try to pick an unused reel to fill the current box
// Case 1 : If sum < box after picking the reel
// => Pick more reels to fill the current box by calling solver recursively
// Case 2 : If sum == box after picking the reel
// => Start with a new box (skill) by calling solver recursively with sum set to 0
// => IMPORTANT : You can do Optimization 2 in this case after returning from solver
if (sum == 0) return false; // Optimization 3
}
return false;
}
int main() {
int T, SUM, ans; // SUM = sum of all reels, ans = total skill number
scanf("%d", &T);
while (T--) {
// Read test case data
// Optimization 1
// Find the answer recursively and print the answer
}
return 0;
}
Input
The first line contains an integer T, represent the number of test cases.
For each test case, the first line is an integer N,
which represents the number of reels LittleBrick has.
The next lines contains N number Xi, separate by spaces,
which represents the number of levels the ith reels can increase to a single skill.
It is guarantee that:
For all test cases:
1 <= T <= 10,
1 <= N <= 100,
1 <= Xi <= 100
For test case 1 ~ 3:
1 <= N <= 10,
For test case 4:
1 <= N <= 100, 1 <= Xi <= 5
For test case 5 & 6:
1 <= N <= 100
Output
For each test case,
output the maximum number of skills LittleBrick can learn,
and a newline character after the answer.