The longest continuous time at least one farmer was milking a cow was 900 seconds (from 300 to 1200. The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 - 1200).
Your job is to write a program that will examine a list of beginning and ending times for N farmers milking N cows and compute (in seconds):
1) The longest time interval at least one cow was milked.
2) The longest time interval no cows were being milked.
The program must read an input file INPUT.C1 and output the solution to the screen.
The first line of the input file is the integer number of farmers N (N <= 32000). The next N lines contain the starting and ending times (in seconds after the starting time 5 am in the morning). These values are integers between 0 and 32,000 inclusive.
SAMPLE INPUT:
3 300 1000 700 1200 1500 2100SAMPLE OUTPUT:
Longest continuous time = 900
Longest idle time = 300
Test your program with the following cases:
Test Case C1.1 10 10 40 50 80 15 25 15 75 45 100 90 120 110 130 140 200 150 170 150 210 Test Case C1.2 23 10 40 30 80 100 150 230 280 290 300 20 50 70 120 160 170 188 250 270 300 40 90 110 160 230 270 70 130 140 171 189 240 260 300 120 160 140 172 190 235 230 275 30 150 220 300 Test Case C1.3 17 100 280 90 200 70 180 60 170 50 150 60 200 50 220 40 240 30 260 20 280 10 300 310 500 320 480 330 470 340 450 350 440 280 310All Test Cases and Answers
NORTH(stall) = (4*stall+ 7) MOD 11If one is in stall 7, then one can move:
SOUTH(stall) = (3*stall+ 1) MOD 11
EAST(stall) = (5*stall+10) MOD 11
WEST(stall) = (9*stall+ 9) MOD 11
(n:2) North to stall 2 (s:0) South to stall 0
(e:1) East to stall 1 (w:6) West to stall 6
Each of stalls 0, 1, 2, and 6 is distance 1 from stall 7. Sometimes two or more doors will lead to the same stall.
Happily, if one goes north from 7 to stall 2, going south from 2 will get back to stall 7.
Given the number of stalls and the formulae above, find any of the `most central' stalls. A stall is `most central' if it is among the stalls that yields the lowest average distance using the best paths to all the other stalls. (See the example below).
Output the stall number and the length of the average path (four decimal places is plenty). Your program must run in under 30 seconds on a Pentium 90 processor.
For each run, the input will be a single line of text with 9 numbers, the prime number p and the eight values corresponding to the parameters (b*stall + c) MOD p in the movement rules above (North, South, East West). Here is the input line for the sample above:
SAMPLE INPUT
11 4 7 3 1 5 10 9 9
Here are the neighboring stalls for sample barn of 11 stalls:
0 e:10 w:9 n:7 s:1 6 e:7 w:8 n:9 s:8
1 e:4 w:7 n:0 s:4 7 e:1 w:6 n:2 s:0
2 e:9 w:5 n:4 s:7 8 e:6 w:4 n:6 s:3
3 e:3 w:3 n:8 s:10 9 e:0 w:2 n:10 s:6
4 e:8 w:1 n:1 s:2 10 e:5 w:0 n:3 s:9
5 e:2 w:10 n:5 s:5
Consider starting from stall 1.
DISTANCE 1: You can get to stalls 4, 7, and 0 in one step
from stall 1, so we say these stalls are distance 1 away.
DISTANCE 2: These are all the stalls you can get to in exactly two steps, so we see where we can get from each of the distance 1 stalls. From stall 4 you can reach 8, 1, and 2; from stall 7 you can reach stalls 1, 6, 2 and 0; and from stall 0 you can reach stalls 10, 9, 7, and 1. Combining these, stalls 0, 1, 2, 6, 7, 8, 9, and 10 are all reachable in 2 steps. But stall 1 was the starting point, and there are shorter paths to 0 and 7; so the remaining stalls (2, 6, 8, 9) are all distance 2 away.
DISTANCE 3: Similarly, we can find stalls 3 and 5 are distance 3 away from stall 1 (and we've covered all the stalls at this point).
The following table summarizes the `shortest path' results:
Dist. Stalls
1 3
2 5
3 2
where `Dist.' is the best distance to some other stall and
`St