Internet Problem Solving Contest

• Students' programs in C++
• Students' programs in Pascal
• Students' programs in Python

Michael is teaching an algorithms class. In the last lecture he gave his students the following problem:

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:

• Alla implemented a brute force solution. She sorts the cubes in descending order. If there are more than 10 15 , she just takes the 10 15 largest cubes. Then she tries all possible ways how to build two towers and finds the best one in which the towers are of equal height.
• Bob finds and outputs the best solution that only leaves at most two cubes unused.

  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.

• Chermi loves greedy algorithms. His program finds the largest X for which his greedy algorithm manages to build two towers of height X each.

  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.

• Dominika’s solution is perhaps the most clever one. She used dynamic programming. For each H she computed the number of ways in which a tower of size H can be assembled. The answer she outputs is the largest X such that the tower of height 2X can be assembled, and the tower of height X can be assembled in at least two different ways.

Problem specification

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.

Input specification

The input file contains implementations of the four students’ programs in C++, Pascal, and Python.

Output specification

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.