TA karN is very busy. Recently, with the regional contests at proximity, a lot of different practice contest are held at different time, with possibly different timespan.
karN would like to participate in them, but there're so many of them it's practically quite impossible to participate in all of them. However there is a good news (for karN maybe, for you uh I'm not so sure): karN is very, very skillful, he is so good that participating in a contest for a consecutive timespan larger than half of the original timespan is enough for him to solve all the problems. For example, suppose a particular contest is held from time 3 to time 11, then karN need only to pick a consecutive timespan of length 5 to finish off all the problems in the contest. Note that karN can only join or leave a contest at integral time, also he always does a contest contiguously and he never do a partial contest.
Now given all the contests (i.e. when they start and finish), determine for karN, at most how many of them could he participate in?
The input consists of several test cases and ends with EOF.
In each test case, the first line contains a integer N, indicating the total number of the weddings. Next follows N integers, each containing two integers Si and Ti indicating the start time and end time of contest i.
For each testcase output a single number on a line, indicating the maximum number of contests karN can participate in.
3 1 5 2 4 3 6 2 1 5 4 6
2 2
This series of homework are all problems with ungiven input size! It is (at least the original aim of it is) to enable us to acutally think about a problem from scratch, without the "additional informations" implicated by a specific given problem size.
Of course, we do hope it'd be a rather fun experience, since in real life problems often we do not know whether a problem exhibits an efficient algorithm or is even solvable!!
Anyway, the input size, though not specified, will be "reasonable". That is, if the optimal algorithm is O(n3), then n would be something like 300, if O(nlgn), then perhaps 200000.. etc. Also if values are not otherwise specified, they could be expected to be for example, int.
Migrated from old NTUJ.
adapted from beijing regional 2008, revised by Kelvin
| No. | Testdata Range | Score |
|---|