Internet Problem Solving Contest

IPSC 2010

Problem F – Flawed Code

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

Given are several cubes of various sizes. You can make towers out of the cubes by placing them one atop another, in any order. Your task is to find the largest possible height H such that is is possible to build two separate towers of height H.

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:

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.