National Olympiad in Informatics, China, 2011
Day 2, Problem 2 - NOI Carnival
NOI 2011 at Jilin University has started! To welcome outstanding informatics competitors from across the country, Jilin University has decided to host two magnificent NOI carnivals at two different venues. Each venue contains many different events, and each event can only be held in one of the venues.
Little Andy, the carnival event organizer, has received a total of n event applications. The i-th event starts at Si and has a duration of Ti. Each events may be scheduled at any one venue, or not scheduled at all.
After extensive surveying, Andy discovered that at any given time if both venues are simultaneously hosting events (excluding the instant when events start or end), competitors will be distraught over deciding between which venue to attend. To prevent this unpleasant scenario, Andy requires that no two events may be simultaneously held at both venues. Multiple events at the same venue may be held as pleased.
As one may imagine, if a certain venue contains too few events, then its appeal will not be so great, leading to an deserted site. Andy wishes to make an appropriate schedule such that the number of events at the venue with the fewest events is as large as possible.
Additionally, some events are very interesting and Andy would like to try to host them. He wishes to know, if the i-th event must be held (it may be held at either one of the venues), what is the maximum number of events than can be held at the venue with the fewest events.
The first line contains an integer n, representing the number of events.
For the following n lines, each line describes a single event. The i-th of these lines will contain two integers Si and Ti, indicating that event i will start at Si and last Ti units of time.
The first line of output should contain a single integer, representing the maximum number of events than can be held at the venue with the fewest events, without any extra restrictions about which event must be held.
The following n lines should each contain a single integer. The i-th of these lines should contain the maximum number of events than can be held at the venue with the fewest events, under the precondition that event i must be held.
5 8 2 1 5 5 3 3 2 5 3
2 2 1 2 2 2
When there are no extra constraints, events 1 and 4 should be scheduled at one venue, and events 3 and 5 should be scheduled at the other venue. event 2 is not scheduled.
For each test case, your score out of 10 is determined as follows:
- If the output format is invalid (e.g. there are fewer than n + 1 lines), then your score will be 0.
- If the first line is incorrect, and at least one of the following n lines is incorrect, then your score will be 0.
- If the first line is correct, but at least one of the following n lines is incorrect, then your score will be 4.
- If the first line is incorrect, but all of the following n lines are correct, then your score will be 6.
- If all n + 1 lines in the output are correct, then your score will be 10.
The attributes of all the test cases are outlined below.
|Test Case||Range of n||Constraints|
|1||1 ≤ n ≤ 10||0 ≤ Si ≤ 109|
1 ≤ Ti ≤ 109
|2||1 ≤ n ≤ 40|
|4||1 ≤ n ≤ 200|
Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 256M
Added: Aug 10, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3