acm
International Collegiate
Programming Contest
event
sponsor
2009
ACM International Collegiate Programming Contest
2009
Latin American Regional Contests
October 23rd-24th, 2009
Contest Session
This problem set contains 11 problems; pages are numbered from 1 to 19.
This problem set is used in simultaneous contests hosted in the following countries:
• Argentina
• Bolivia
• Brazil
• Chile
• Colombia
• Cuba
• Peru
• Mexico
• Venezuela
Version 6
ACM ICPC2009 – Latin American Regionals 1
Problem A
Another Crisis
File code name: another
A couple of years ago, a new world wide crisis started, leaving many people with economical
problems. Some workers of a particular company are trying to ask for an increase in their
salaries.
The company has a strict hierarchy, in which each employee has exactly one direct boss, with
the exception of the owner of the company that has no boss. Employees that are not bosses
of any other employee are called workers. The rest of the employees and the owner are called
bosses.
To ask for a salary increase, a worker should file a petition to his direct boss. Of course,
each boss is encouraged to try to make their subordinates happy with their current income,
making the company’s profit as high as possible. However, when at least T percent of its direct
subordinates have filed a petition, that boss will be pressured and have no choice but to file
a petition himself to his own direct boss. Each boss files at most 1 petition to his own direct
boss, regardless on how many of his subordinates filed him a petition. A boss only accounts his
direct subordinates (the ones that filed him a petition and the ones that didn’t) to calculate
the pressure percentage.
Note that a boss can have both workers and bosses as direct subordinates at the same time.
Such a boss may receive petitions from both kinds of employees, and each direct subordinate,
regardless of its kind, will be accounted as 1 when checking the pressure p ercentage.
When a petition file gets all the way up to the owner of the company, all salaries are increased.
The workers’ union is desperately trying to make that happen, so they need to convince many
workers to file a petition to their direct boss.
Given the company’s hierarchy and the parameter T , you have to find out the minimum number
of workers that have to file a petition in order to make the owner receive a petition.
Input
There are several test cases. The input for each test case is given in exactly two lines. The
first line contains two integers N and T (1 ≤ N ≤ 10
5
, 1 ≤ T ≤ 100), separated by a single
space. N indicates the number of employees of the company (not counting the owner) and T
is the parameter described above. Each of the employees is identified by an integer between 1
and N . The owner is identified by the number 0. The second line contains a list of integers
separated by single spaces. The integer B
i
, at position i on this list (starting from 1), indicates
the identification of the direct boss of employee i (0 ≤ B
i
≤ i − 1).
The last test case is followed by a line containing two zeros separated by a single space.
Output
For each test case output a single line containing a single integer with the minimum number
of workers that need to file a petition in order to get the owner of the company to receive a
petition.
ACM ICPC2009 – Latin American Regionals 2
Sample input
3 100
0 0 0
3 50
0 0 0
14 60
0 0 1 1 2 2 2 5 7 5 7 5 7 5
0 0
Output for the sample input
3
2
5
ACM ICPC2009 – Latin American Regionals 3
Problem B
Brothers
File code name: brothers
In the land of ACM ruled a great King who became obsessed with order. The kingdom had a
rectangular form, and the King divided the territory into a grid of small rectangular counties.
Before dying, the King distributed the counties among his sons.
However, he was unaware that his children had developed a strange rivalry: the first heir hated
the second heir, but not the rest; the second heir hated the third heir, but not the rest, and so
on . . . Finally, the last heir hated the first heir, but not the other heirs.
As soon as the King died, the strange rivalry among the King’s sons sparked off a generalized
war in the kingdom. Attacks only took place between pairs of adjacent counties (adjacent
counties are those that share one vertical or horizontal border). A county X attacked an
adjacent county Y whenever the owner of X hated the owner of Y . The attacked county was
always conquered by the attacking brother. By a rule of honor all the attacks were carried out
simultaneously, and a set of simultaneous attacks was called a battle. After a certain number
of battles, the surviving sons made a truce and never battled again.
For example, if the King had three sons, named 0, 1 and 2, the figure below shows what happens
in the first battle for a given initial land distribution:
You were hired to help an ACM historian determining, given the number of heirs, the initial
land distribution and the number of battles, what was the land distribution after all battles.
Input
The input contains several test cases. The first line of a test case contains four integers N, R,
C and K, separated by single spaces. N is the number of heirs (2 ≤ N ≤ 100), R and C are the
dimensions of the kingdom (2 ≤ R, C ≤ 100), and K is the number of battles (1 ≤ K ≤ 100).
Heirs are identified by sequential integers starting from zero (0 is the first heir, 1 is the second
heir, . . ., N − 1 is the last heir). Each of the next R lines contains C integers H
r,c
separated
by single spaces, representing initial land distribution: H
r,c
is the initial owner of the county in
row r and column c (0 ≤ H
r,c
≤ N − 1).
The last test case is followed by a line containing four zeroes separated by single spaces.
ACM ICPC2009 – Latin American Regionals 4
Output
For each test case, your program must print R lines with C integers each, separated by single
spaces in the same format as the input, representing the land distribution after all battles.
Sample input
3 4 4 3
0 1 2 0
1 0 2 0
0 1 2 0
0 1 2 2
4 2 3 4
1 0 3
2 1 2
8 4 2 1
0 7
1 6
2 5
3 4
0 0 0 0
Output for the sample input
2 2 2 0
2 1 0 1
2 2 2 0
0 2 0 0
1 0 3
2 1 2
7 6
0 5
1 4
2 3
