517 . JAGODA
Description
Slavko has N rabbits that he feeds every day with various fruits and vegetables. Rabbits, however,
prefer strawberries above all else. Strawberries are hard to find and expensive in the middle of winter,
so Slavko only gives strawberries to part of his rabbits.
Slavko numbered the rabbits 1 through N. To help keep track of how many strawberries each of the
rabbits got, Slavko decided on the following strawberry allocation procedure.
Every day Slavko purchases some number S of strawberries and chooses some rabbit A to get the first
strawberry. Rabbit A+1 will get the second strawberry, rabbit A+2 the third etc.
Every rabbit is assigned an initially empty matchbox, the N matchboxes forming a single row.
Let K be the largest integer such that K*K ≤ N. Every group of K matchboxes (starting with the first)
will also have a cup next to them. We say that K consecutive matchboxes with their cup form a block.
After giving the rabbits their strawberries, Slavko will put a single match into the matchbox of every
rabbit that got a strawberry, unless he would be putting a match into all matchboxes in a block.
Instead of putting matches into all matchboxes in a block, he will put a single match in the appropriate
cup.
The total number of strawberries received by a rabbit can be calculated as the number of matches in its
matchbox plus the number of matches in its cup.
For example, assume that there are 11 rabbits, that is N=11. The number three is the largest integer
which, when squared, gives a result of at most 11, so K=3. There will be four blocks, the last of them
incomplete with only two matchboxes. If Slavko buys 6 strawberries and gives the first of them to
rabbit 5, the state in the cups and matchboxes will be:
Write a program that simulates the above procedure, knowing the number of rabbits N, the number of
days M and the numbers S and A for each of the M days.
For every day, output the total number of matches in all matchboxes and cups that Slavko added
matches to on that day.
Input Format
There are multiple test cases in the input file, terminated by EOF. For every test case:
The first line contains the integers N and M separated by a space (1 ≤ N, M ≤ 100 000), the number of
rabbits and days.
Each of the following M lines contains two integers S and A separated by a space. These numbers
mean that Slavko purchased S strawberries that day and that rabbit A will receive the first one
(1 ≤ A ≤ N, 1 ≤ A+S–1 ≤ N).
Output Format
Output M numbers, each on a separate line. The k- th line should contain the total number of matches
in all matchboxes and cups that Slavko used on day k.
There is no need to print any blank lines between test cases.
Sample Input 1
11 3 6 5 3 1 11 1 16 3 2 2 12 3 6 11
Sample Output 1
4 1 6 2 7 3
Hints
In the first example, there are 11 rabbits and matchboxes, and four blocks, as shown in the image on
the previous page.
- On the first day, Slavko gives strawberries to rabbits 5 through 10, putting matches into
matchboxes 5, 6 and 10, and one into the third cup. Before this there were no other matches in
the matchboxes and cups he used, so the output is four. - On the second day, Slavko gives strawberries to rabbits 1 through 3, putting just one match into
the first cup. - On the third day, Slavko gives strawberries to all his rabbits, putting one match into every cup.
- After putting the four matches into cups, there is a total of six matches in the cups he used, so
the output is six.
Problem Source
Migrated from old NTUJ.
COCI2008/2009 contest #5
Subtasks
| No. | Testdata Range | Score |
|---|