CEOI'98 Logo

Cake 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 following entries were submmitted for The Cake Contest:

  • Croatia (all teams together)
  • Czech Republic
  • Germany
  • Slovak Republic
Most of the teams submitted more than one problem (they probably thought that their chances of wining the cake will increase with number of problems).

Members of The Cake Committee were:

President: Tomislav Zganec, Ph. D. in cake eating

  • Branka Sacher
  • Elinka Barisic
  • Marijana Grgek
At the session today at noon, after having spent some time drooling over the cake, they have reached the verdict: All of the problems are poorly written, unimaginative and donít make any sense. Thatís why The Cake Committee decided noone should win, and that they should eat the cake.

Made you look, eh!? Just kidding, The Cake Committee are nice guys (and gals), so the cake is still safe and sound. Although, the winner is obliged to give part of The Cake to the committee, because they had such a tough job in selecting the right problem ;)

Unfortunately, noone sent in the problem that would deal with the rain, but the problem they chose was the most imaginative and most applicable to CEOI. And, finally:

The Winner of The Grand Cake Contest at the CEOI í98 is:

The German Team

Hereís the winning problem:

Problem description

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:

    An actual distance matching the favourite distance increases the happiness of the participant by 30. The happiness decreases by the difference between actual and favourite distance. If, for example, Alice prefers sitting in a distance of 5 to Bob, while Bob is sitting 3 rows in front of Alice, i.e. at a distance of 4, happiness of Alice will be increased by 29. Note that the favourite distance from Alice to Bob can differ from the favourite distance from Bob to Alice. Since we are at a CEOI, no individual happiness will become less than 0.
Input data

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.

Output data

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

   4 1 3 2 
   0 5 1 2 
   1 0 1 1 
   2 1 0 6 
   3 1 1 0