NWERC 2010
The 2010 ACM Northwestern Europe Programming Contest
The Problem Set
A Fair Division
B Free Goodies
C High Score
D Hill Driving
E Rankings
F Risk
G Selling Land
H Stock Prices
I Telephone Network
J Wormly
These problem texts are copyright by the NWERC 2010 jury. They are licensed under the
Creative Commons Attribution-Share Alike license version 3.0; The complete license text can
be found at: http://creativecommons.org/licenses/by-sa/3.0/legalcode
Contact us if you’d like to receive the LaTeX sources.
Problem A: Fair Division 1
A Fair Division
It’s your friend’s birthday, and you and some other people decided to buy him a copy of
StarCraft II, because who wouldn’t want to have that?
You agreed to divide the costs as fairly as possible. Since some of you have more money
available than others, you also agreed that nobody has to pay more than he can afford. Every
contribution will be a multiple of 1 cent, i.e., nobody can pay fractions of a cent.
Everybody writes down the maximum amount he is able to contribute. Taking into ac-
count these maximum amounts from everybody, you share the cost of the present as fairly as
possible. That means, you minimize the largest distance of the contributions to
1
n
-th of the
total cost. In case of a tie, minimize the second largest distance, and so on. Since the smallest
unit of contribution is 1 cent, there might be more than one possible division of the cost. In
that case, persons with a higher maximum amount pay more. If there is still ambiguity, those
who come first in the list pay more.
Since you bought the present, it is your task to figure out how much everybody has to pay
(including you).
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test
case:
• One line with two integers p and n: the price of the present in cents (1 ≤ p ≤ 1 000 000)
and the number of people (2 ≤ n ≤ 100) who contribute to the present (including you).
• One line with n integers a
i
(1 ≤ a
i
≤ 1 000 000), where a
i
is the maximum amount, in
cents, that the i-th person on the list is able to contribute.
Output
Per test case:
• One line with n integers: the amounts each person has to contribute according to the
scheme. If the total cost cannot be divided according to the above rules, the line must
contain “IMPOSSIBLE” instead.
Sample in- and output
Input Output
3
20 4
10 10 4 4
7 3
1 1 4
34 5
9 8 9 9 4
6 6 4 4
IMPOSSIBLE
8 7 8 7 4
Almost blank page
Problem B: Free Goodies 3
B Free Goodies
Petra and Jan have just received a box full of free goodies, and want to divide the goodies
between them. However, it is not easy to do this fairly, since they both value different goodies
differently.
To divide the goodies, they have decided upon the following procedure: they choose
goodies one by one, in turn, until all the goodies are chosen. A coin is tossed to decide who
gets to choose the first goodie.
Petra and Jan have different strategies in deciding what to choose. When faced with a
choice, Petra always selects the goodie that is most valuable to her. In case of a tie, she is
very considerate and picks the one that is least valuable to Jan. (Since Petra and Jan are good
friends, they know exactly how much value the other places on each goodie.)
Jan’s strategy, however, consists of maximizing his own final value. He is also very con-
siderate, so if multiple choices lead to the same optimal result, he prefers Petra to have as
much final value as possible.
You are given the result of the initial coin toss. After Jan and Petra have finished dividing
all the goodies between themselves, what is the total value of the goodies each of them ends
up with?
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test
case:
• One line with an integer n (1 ≤ n ≤ 1 000): the number of goodies.
• One line with a string, either “Petra” or “Jan”: the person that chooses first.
• n lines with two integers p
i
and j
i
(0 ≤ p
i
, j
i
≤ 1 000) each: the values that Petra and Jan
assign to the i-th goodie, respectively.
Output
Per test case:
• One line with two integers: the value Petra gets and the value Jan gets. Both values
must be according to their own valuations.
