JANICA
InterviewTime limit1sMemory limit128 MB
Reconstruct running leader times from cumulative differences over two ski rounds to find the top three finishers by total time.
- Level
Medium5 of 10
- Topics
- Simulation, Sorting, Implementation
- Solved
- No attempts yet
Problem
An alpine skiing race can be dull to watch on television. If the broadcast does not show every piece of information, you may have to compute the winner yourself.
The race has two rounds. In the first round, skiers numbered from 1 to N start in increasing order of their numbers.
When skier 1, the first skier in the first round, finishes, that skier's time is given. For each following skier, the input gives the difference between that skier's time and the time of the skier who was leading just before that skier finished. A smaller time is better.
Only the best M skiers after the first round qualify for the second round. Their second-round starting order is decreasing by first-round time. In other words, the slowest qualifier starts first, and the first-round leader starts last.
In the second round, the total time of the first starter is given. This total time is the sum of the first and second round times. For each following skier, the input gives the difference between that skier's total time and the total time of the skier who was leading just before that skier finished.
After the race ends, determine the skier numbers that won the gold, silver, and bronze medals. No two skiers have the same first-round time, and no two skiers have the same total time after both rounds.
Every time is between 10 and 300 seconds, inclusive, and has at most two digits after the decimal point.
Input
The first line contains two integers N and M, separated by one space. 3 <= M <= N <= 100.
The next line contains skier 1's time in the first round. The following N-1 lines contain the described time differences in skier-number order.
The next line contains the total time of the first skier to start in the second round. The following M-1 lines contain the described total-time differences in second-round starting order.
Output
Print the number of the gold medalist on the first line. Print the number of the silver medalist on the second line, and the number of the bronze medalist on the third line.