The Cake Contest was a special competition for teams, were they should think of the best problem for CEOI competition. It was named The Cake Contest after the reward. The Winner of The Grand Cake Contest at the CEOI ’98 is The German Team.
Here’s the winning problem:
N participants of the CEOI should be transported to a national park. They travel in B busses with L seating rows of S seats each, with N <= (B*L*S). The distance between two people sitting next to each other is 1. The distance between people sitting in the same row but not next to each other is 2 and the distance between people sitting M rows apart from each other, but in the same bus, is (M+1). People in different busses always have a distance of 20.
Your goal is to maximise the happiness of the CEOI participants. Each participant has a certain favourite distance to those participants he or she already knows. Participants do not care about distances to people they do not yet know. Global happiness is the sum over all individual happinesses. Individual happiness of a participant is calculated as follows:
The first line of the input file VOTE4ME.IN contains the positive integers N <= 10000, B <= 100, L < 30 and S <= 10. The following N lines of the input file contain N numbers each. The number I, 0<= I <= 30, in column U and row V is the distance that participant V would like participant U to sit. The favourite distance from a participant to him/herself is always 0; instead of real distances to people he or she does not know, the input file will contain the special value 1.
The output file VOTE4ME.OUT must consist of N lines, line j, 1 <= j <= N containing the happiness of person j in an optimal sitting plan. An optimal sitting plan is one that maximises the global happiness. Examples
VOTE4ME.IN 4 1 3 2 0 5 1 2 1 0 1 1 2 1 0 6 3 1 1 0 VOTE4ME.OUT 25 29 26 30