Segway
레이팅 미적용의견: 0
Croatian Olympiad in Informatics 2019.
Page 6 of 9
There is a Segway race in the city of Dubrovnik. The race track consists of three sections, each of
which is 100 meters long – therefore, the total length of the track is 300 meters. Based on the
limitations of h\(er/hi\)s Segway battery, each rider has a strategy: the speed at which he rides on the first
100 meters, the speed on the next 100 meters, and the speed on the last 100 meters, except when
allowed to speed up the Segway to the maximum speed (explained in the next paragraph).
Unfortunately, the Segways are very slow, taking between 1 and 50 seconds for each meter. Therefore,
the speeds in this task are given in seconds per meter (instead of meters per second).
Along the track there are several acceleration points (accelerators). When a rider reaches an accelerator,
his Segway gets extra power to ride at the maximum speed of 1 second per meter for the next
X mod 20 meters, where X is the number of riders strictly ahead of him at the moment he reached the
accelerator (including those who have already completed the race). The rider is unable to use another
accelerator before he has spent all extra power from the previous accelerator. At that moment, if there
are no new accelerators, the rider continues to move at his default speed for the corresponding track
section.
Assume that a rider will always use an available accelerator, even if it might not be the optimal strategy.
An accelerator can be use by multiple riders, even at the same time. Your task is to write a program that
simulates this race. Assuming that all Segway riders start at the same time, print the finish time for each
rider in seconds.
subtask
points
additional constraints
1
15
\(M = 1\)
2
40
\(N \le 300\)
3
45
no additional constraints
(See examples on the next page.)
Croatian Olympiad in Informatics 2019.
Page 7 of 9
The first line contains an integer N (\(2 \le N \le 20\,000\)), the number of riders.
The K^{th} of the following N lines contains three integers between 1 and 50: the default speed of the
K^{th} rider on the first 100 meters, the next 100 meters, and the last 100 meters of the track.
The next line contains an integer M (\(0 \le M \le 299\)), the number of acceleration points.
If \(M > 0\), the following line contains a strictly increasing sequence of M integers between 1 and 299: the
distances of the accelerators from the beginning of the track in meters.
You should print N lines, where the K^{th} line contains the required time for the K^{th} rider.
2
1 2 3
4 5 6
0600
15003
5 5 5
6 2 10
10 9 2
2
100 1991496
1799
20755
2 2 2
6 6 6
8 8 8
9 9 9
10 10 10
2
297 298600
1790
2386
2676
2973
First sample description: There are no accelerators and both riders use their default speeds.
Second sample description: Rider #1 does not use the first accelerator (there is nobody ahead of
him), but uses the second accelerator because rider #2 overtakes him in the meantime. Overall, rider
#1 rides 299 meters for 5 seconds each, and 1 metar for 1 second.
Rider #2 uses the first accelerator (there is one rider ahead), but does not use the second one. Overall,
he rides 100 meters for 6 seconds each, 1 meter for 1 second, 99 meters for 2 seconds each, and 100
meters for 10 second each.
Rider #3 after each accelerator rides 2 meters at maximum speed. Overall, he rides 100 meters for 10
seconds each, 2 meters for 1 second each, 97 meters for 9 seconds each, 2 meters for 1 second each,
and 99 meters for 2 seconds each.
Third sample description: Of the two accelerators near the end of the track, rider #1 does not use
any. Rider #2 uses both (for 1 meter) and then rides for another 1 meter at her default speed. Rider #3
uses the first accelerator (for 2 meters) and then rides for another 1 meter at her default speed. Riders
#4 and #5 use extra power from the first accelerator all the way to the end of the track.평가 및 의견
Segway
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Segway