There is a large number of empty bins in a factory depot. The bins are arranged in a single
row. The manager of the depot wants to put some bins into other bins to make some free space
in the left end of the depot. Bins can be moved by a robot, which can take a bin, carry it to
the right, and put it into a larger bin. This three-operation sequence is the only allowed way to
move bins.
Because of safety regulations, any bin can contain at most one other bin, which must be empty.
The manager also wants to keep the double bins in the left end of the resulting row, to make it
easier to keep track of them.
You are to write a program that computes the largest possible K such that the K leftmost bins
can be put into the immediately following K bins in some order.
The first line of the input contains an integer T indicating the number of test cases. For each test case, the first line an integer N, the number of bins. The second line contains N integers Ai, separated by spaces: the sizes of the bins, listed from left to right.
For each test case output a line containing a single integer, the
largest number K such that the robot can put the K leftmost bins into the next K bins.
1 10 2 2 1 4 3 2 5 4 2 3
4
This series of homework are all problems with ungiven input size! It is (at least the original aim of it is) to enable us to acutally think about a problem from scratch, without the "additional informations" implicated by a specific given problem size.
Of course, we do hope it'd be a rather fun experience, since in real life problems often we do not know whether a problem exhibits an efficient algorithm or is even solvable!!
Anyway, the input size, though not specified, will be "reasonable". That is, if the optimal algorithm is O(n3), then n would be something like 300, if O(nlgn), then perhaps 200000.. etc. Also if values are not otherwise specified, they could be expected to be for example, int.
Migrated from old NTUJ.
BOI improved
| No. | Testdata Range | Score |
|---|