Pod starim krovovima
레이팅 미적용의견: 0
Setting: Legendary Zagrebian Inn called Kod Žnidaršića.
Time: The year 1936.
Plot summary: Franjo and his friends are discussing the current events in Abyssinia
while enjoying a couple of drinks at the bar. His son, little Perica, is sitting at a small
table in the corner of the bar. In front of Perica there are \(N\) glasses conveniently
numbered from 1 to \(N\). The volume (in nanoliters) of each glass is known as well as
the amount of liquid that is currently inside it.
Problem: Little Perica wants to know what is the largest possible number of glasses that can be emptied
by pouring the liquid between glasses. He can freely pour any integer number of nanoliters from one glass
to another, as many times as he wants, as long as no liquid is spilled over.
Your task is to output the number of empty glasses along with one possible configuration of liquid in all
glasses. If there are multiple configurations that yield the same number of empty glasses, output any
of them. Note that it is not necessary to minimize the number of times liquid was poured between two
glasses.
Correctly written first line is worth 4 points, and correctly written second line is worth 1 point for each
test case.
In test cases worth a total of 20 points, all glasses will have the same volume.
The first line contains an integer \(N\) (\(1 \le N \le 1\,000\)) from the task description.
Each of the next \(N\) lines contains two integers \(T@@RISE_MATH_BLOCK_0@@i \le 10^{9}\)) and \(Z@@RISE_MATH_BLOCK_1@@i \le 10^{9}\)) which, in that
order, represent the current amount of liquid in the \(i-th\) glass and its volume. Both quantities are given in
nanoliters and the current amount of liquid cannot be greater than the volume of the glass, i.e. \(T@@RISE_MATH_BLOCK_2@@i\)
holds.
In the first line you should output the largest number of glasses that can be emptied by pouring the liquid
between glasses.
In the second line you should output the amount of liquid in each of the glasses after Perica has performed
the necessary pourings. The glasses should be ordered from glass numbered 1 to glass numbered \(N\).
5
2 6
1 6
0 6
6 6
5 62
6 6 2 0 05
4 5
2 7
5 5
0 10
7 93
0 0 0 10 88
2 6
3 4
1 1
9 10
0 10
4 5
6 8
3 95
0 0 0 9 10 0 0 9Clarification of the second example: One of the possible pouring configurations is the following:
1. pour everything from glass 1 into glass 2.
2. pour everything from glass 2 into glass 4.
3. pour four nanoliters from glass 3 into glass 4.
4. pour one nanoliter from glass 3 into glass 5.
Glasses numbered 1, 2 and 3 are now empty.
평가 및 의견
Pod starim krovovima
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Pod starim krovovima