WatchedSnail
SRM 810 · 2021-07-22 · by misof
Problem Statement
A snail was racing along a straight trail for raceTime seconds. The snail maintained the same direction during the entire race. On the other hand, its speed during the race was not necessarily constant.
The race had observerCount observers. Each of them watched the snail during a single contiguous closed interval that measured exactly observationTime seconds.
(No observation started before the start of the race. No observation ended after the end of the race. Some observers could have started and therefore also ended their observation at a non-integer timestamp.)
It is guaranteed that during the entire race the snail was always observed by at least one person. Each observer came to the same conclusion: the distance traveled by the snail during their observation was exactly observationDistance inches.
Return the maximum distance in inches the snail could have traveled during the entire race.
Notes
- Your return value will be accepted if it has an absolute or a relative error at most 10^(-9).
- The snail cannot teleport (move at infinite speed). Its position in time is a continuous non-decreasing function.
- As implied by the "non-decreasing" in the previous sentence, the snail may stand still during some intervals of time.
Constraints
- raceTime will be between 1 and 1000, inclusive.
- observerCount will be between 1 and 1000, inclusive.
- observationTime will be between 1 and raceTime, inclusive.
- observationDistance will be between 1 and 1000, inclusive.
- observerCount * observationTime will be greater than or equal to raceTime.
100 3 100 47 Returns: 47.0
Each person observed the snail during the entire race and saw the snail traverse 47 inches.
100 10 10 47 Returns: 470.0
Ten people took turns watching the snail. Each person saw the snail traverse 47 inches, so the snail traversed 470 inches total. Boring.
100 8 20 47 Returns: 376.0
This should be obvious, right? Each observation took 20 seconds. The distance traveled during each observation is 47 inches, so for each observation the snail had an average speed of 2.35 inches per second. The whole race was 100 seconds and at that average speed the snail must have travelled 2.35 * 100 = 235 inches. The snail was always watched, so it could not have... wait, what?
100 2 74 47 Returns: 94.0
One observer started at the beginning of the race and one ended at the end of the race. If [0,100] is the time interval of the race, the first observer was active during [0,74] and the second one during [26,100]. It is possible that the snail traversed only 47 inches total, but it is also possible that it traversed more. The largest possible total distance it could have travelled is obviously 94 inches. The answer would clearly remain 94 inches even if we had more than two observers (while keeping the other three parameters the same).
60 47 10 10 Returns: 100.0
Submissions are judged against all 140 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WatchedSnail with a public method double maxDistance(int raceTime, int observerCount, int observationTime, int observationDistance) · 140 test cases · 2 s / 256 MB per case