**********************************************************************
GOLD PROBLEMS
**********************************************************************
Three problems numbered 1 through 3
**********************************************************************
Problem 1: Balanced Lineup [Coaches, 2004]
For the daily milking, Farmer John's N cows (1 <= N <= 50,000)
always line up in the same order. One day Farmer John decides to
organize a game of Ultimate Frisbee with some of the cows. To keep
things simple, he will take a contiguous range of cows from the
milking lineup to play the game. However, for all the cows to have
fun, they should not differ too much in height.
Farmer John has made a list of Q (1 <= Q <= 180,000) potential
groups of cows and their heights (1 <= height <= 1,000,000). For
each group, he wants your help to determine the difference in height
between the shortest and the tallest cow in the group.
Note: on the largest test case, I/O takes up the majority of the
runtime.
PROBLEM NAME: lineupg
INPUT FORMAT:
* Line 1: Two space-separated integers, N and Q.
* Lines 2..N+1: Line i+1 contains a single integer that is the height
of cow i
* Lines N+2..N+Q+1: Two integers A and B (1 <= A <= B <= N),
representing the range of cows from A to B inclusive.
SAMPLE INPUT (file lineupg.in):
6 3
1
7
3
4
2
5
1 5
4 6
2 2
OUTPUT FORMAT:
* Lines 1..Q: Each line contains a single integer that is an answer to
an input query and tells the difference in height between the
tallest and shortest cow in the input range.
SAMPLE OUTPUT (file lineupg.out):
6
3
0
**********************************************************************
Problem 2: Problem Solving [Hal Burch, 2004]
In easier times, Farmer John's cows had no problems. These days,
though, they have problems, lots of problems; they have P (1 <= P
<= 300) problems, to be exact. They have quit providing milk and
have taken regular jobs like all other good citizens. In fact, on
a normal month they make M (1 <= M <= 1000) money.
Their problems, however, are so complex they must hire consultants
to solve them. Consultants are not free, but they are competent:
consultants can solve any problem in a single month. Each consultant
demands two payments: one in advance (1 <= payment <= M) to be paid
at the start of the month problem-solving is commenced and one more
payment at the start of the month after the problem is solved (1
<= payment <= M). Thus, each month the cows can spend the money
earned during the previous month to pay for consultants. Cows are
spendthrifts: they can never save any money from month-to-month;
money not used is wasted on cow candy.
Since the problems to be solved depend on each other, they must be
solved mostly in order. For example, problem 3 must be solved
before problem 4 or during the same month as problem 4.
Determine the number of months it takes to solve all of the cows'
problems and pay for the solutions.
PROBLEM NAME: psolve
INPUT FORMAT:
* Line 1: Two space-separated integers: M and P.
* Lines 2..P+1: Line i+1 describes problem i with two space-separated
integers: B_i and A_i. B_i is the payment to the consult
BEFORE the problem is solved; A_i is the payment to the
consult AFTER the problem is solved.
SAMPLE INPUT (file psolve.in):
100 5
40 20
60 20
30 50
30 50
40 40
INPUT DETAILS:
The cows make 100 money each month. They have 5 problems to solve,
which cost 40, 60, 30, 30, and 40 in advance to solve and then 20,
20, 50, 50, and 40 at the beginning of the month after the problems
are solved.
OUTPUT FORMAT:
* Line 1: The number of months it takes to solve and pay for all the
cows' problems.
SAMPLE OUTPUT (file psolve.out):
6
OUTPUT DETAILS:
+------+-------+--------+---------+---------+--------+
| | Avail | Probs | Before | After | Candy |
|Month | Money | Solved | Payment | Payment | Money |
+------+-------+--------+---------+---------+--------+
| 1 | 0 | -none- | 0 | 0 | 0 |
| 2 | 100 | 1, 2 | 40+60 | 0 | 0 |
| 3 | 100 | 3, 4 | 30+30 | 20+20 | 0 |
| 4 | 100 | -none- | 0 | 50+50 | 0 |
| 5 | 100 | 5 | 40 | 0 | 60 |
| 6 | 100 | -none- | 0 | 40 | 60 |
+------+-------+--------+---------+---------+--------+
**********************************************************************
Problem 3: Cow School [Jacob Steinhardt, 2006]
Bessy is going to school and doing well. She has taken N (1 <= N
<= 5000 -- except one case where 1 <= N <= 50,000) tests and recorded
the scores (T_i points out of P_i points for test i; 0 <= T_i <=
P_i < 40,000; 0 < P_i) as this task's input.
Her teacher will drop the D tests with the lowest percentage (T_i/P_i)
before calculating Bessie's final grade (which is the sum of the
remaining test score points over the sum of the remaining total
test points). Bessy is good at math and quickly realizes that this
does not benefit her as much as it might.
To prove her point, Bessy wants to find all values of D for which
she could have ended up with a higher grade by choosing to drop
different tests than the teacher would have. Help her by finding
and printing all values of D for which this is possible.
Bessy has noted that, amazingly, she has never scored the same
percentage on two different tests.
PROBLEM NAME: schul
INPUT FORMAT:
* Line 1: A single integer, N
* Lines 2..N+1: Line i+1 contains two space-separated integers: T_i
and P_i
SAMPLE INPUT (file schul.in):
5
1 2
5 9
3 8
4 10
1 3
INPUT DETAILS:
Bessy has taken 5 tests so far and has scores of 1/2, 5/9, 3/8, 4/10, and 1/3.
OUTPUT FORMAT:
* Line 1: A single integer K (0 <= K <= N) that is the number of
values of D for which Bessy could have ended up with a higher
grade by dropping a different set of D tests than the teacher.
* Lines 2..K+1: The values of D for which this is true, in ascending
numerical order.
SAMPLE OUTPUT (file schul.out):
2
1
2
OUTPUT DETAILS:
For D = 1, dropping 1/3 leads to a final grade of 13/29. A higher
final grade of 11/24 can be achieved if Bessy drops 3/8.
For D = 2, dropping 1/3 and 3/8 lead to a final grade of 10/21. A
higher final grade of 7/14 can be achieved if Bessy drops 3/8 and
4/10.
**********************************************************************