Michael is teaching an algorithms class. In the last lecture he gave his students the following problem:
For example, if the cube sizes are (8,6,3,3,3,2), then the solution is 11:
we can build one tower as 8+3, the other as 6+3+2, and a cube of size 3 remains unused.
This task proved to be too difficult for his students, so each of them just implemented some clever hack that sometimes worked and sometimes failed. More precisely:
To do so, he used dynamic programming to implement a function that takes a set of cubes and checks whether it is possible to build two equal towers using all of them. He then calls this function multiple times, each time with a different subset of the given set of cubes.
His algorithm to build two towers of height X is simple: He first sorts the cubes in descending order, and then processes them one by one. Each time he checks whether he can add the cube to the currently smaller tower without exceeding X, and if he can, he does so.
You are given the four programs made by Michael’s students (for your convenience, each of them is implemented in several languages). Your goal is to help Michael show the students their errors by providing inputs for which the students’ solutions fail.
The input file contains implementations of the four students’ programs in C++, Pascal, and Python.
As the output for the easy data set F1, output 4 lines, containing 2 valid test cases. Each test case consists of two lines. The first line contains the number N of cubes (1 ≤ N ≤ 100). The second line contains N space-separated integers – the cube sizes. The sum of all cube sizes must not exceed 10000.
The submission will be judged as correct if it breaks at least three of our solutions. In other words, at most one of our four solutions can give the correct answer for both your test cases.
As the output for the hard data set F2, output 2 lines containing a single valid test case.
The submission will be judged as correct if it breaks all four solutions. That is, none of the four solutions should give the correct answer for your test case.