In a candy factory, there is a mysterious machine. It produces delicious candies, each a little bit
different from the others. The machine has a line of output slots, numbered 1 to n, from which the
candies fall out as soon as they are ready. No one really knows how the machine works, but before
it starts a production session, it prints a list telling the factory owner, when and from which slot each
candy will fall out.
Now, the factory owner can install automatic wagons that move below the output slots to catch the
falling candies. Of course, none of the candies should drop on the floor and get spoilt. However, since
running the wagons is expensive, the owner would like to install as few wagons as possible.
Write a program that computes the minimum number of wagons needed to catch all candies. More-
over, your program shall output which wagon should catch which candy. The wagons run at a speed
of one slot width per second. Before the production process starts, each wagon can be moved to the
slot where it should catch its first candy.
There are multiple test cases in the input file. For each test case:
The input is read from standard input, and describes one production session of the machine. The
first line contains exactly one integer n, the number of candies produced in that session. Each of the
following n lines contains a pair of integers si and ti, output slot and time for candy i. Each pair
(si, ti) is unique.
1<=n<=100,000
0<=si,ti<=1,000,000,000
Output should be written to standard output. The first line of the each output contains exactly one integer
w, the minimum number of wagons needed to catch all candies.
5 1 1 2 3 1 5 3 4 2 6 5 1 1 2 3 1 5 3 4 2 6
2 2
Migrated from old NTUJ.
BOI2009
| No. | Testdata Range | Score |
|---|