EllysRain
TCC India 2018 Qual · 2018-06-29 · by espr1t
Problem Statement
Elly has a beautiful flowerpot with roses on her window sill. Whenever it rains outside, Elly remembers that she hasn't watered her roses in a while. However, now that it rains, maybe the rain will water them for her! To make sure the roses get watered properly, Elly watches the whole situation carefully and records where the individual raindrops fall.
For simplicity, we will consider the flowerpot to be a closed line segment of length L. (One endpoint of the segment has coordinate 0, the other has coordinate L, and both endpoints belong to the segment.) Each raindrop will fall onto some point of this segment. The coordinate of each raindrop will be an integer.
The flowerpot is considered properly watered if each possible closed interval of length D or more already received at least one raindrop. Note that this includes intervals that start and end at non-integer coordinates.
You are given the
Find and return the smallest K such that Elly's flowerpot was properly watered after the first K raindrops. If the entire rainfall was not enough to water the flowerpot properly, return -1 instead.
Constraints
- L will be between 2 and 1,000,000,000, inclusive.
- D will be between 1 and L-1, inclusive.
- N will be between 1 and 1,000,000, inclusive.
- P1, M, and A will each be between 0 and L, inclusive.
23 7 12 14 13 5 Returns: 9
We have a flowerpot of length L = 23, and we are waiting until each closed interval of length D = 7 or more gets hit by a raindrop. There are N = 12 raindrops. Using the formula from the problem statement we can compute that their coordinates are 14, 19, 12, 17, 10, 15, 8, 13, 6, 11, 4, 9 (in this order). First eight raindrops are not enough. For example, there is a completely dry interval of length 7.3 that starts at coordinate 0.4 and ends at coordinate 7.7. On the other hand, the first nine raindrops are already enough. Thus, the correct return value is 9.
10 4 5 5 2 6 Returns: -1
This flowerpot has length 10. There are 5 raindrops, and each of them falls on the same coordinate: at 5. We need to water every interval of length 4 or more, but after the last raindrop the interval [6,10] is still all dry. Thus, the flowerpot is still not watered properly and we should return -1.
10 5 5 5 2 6 Returns: 1
Sometimes a single drop of water is all Elly's cactuses need.
1000000 1337 123456 424242 13 42 Returns: 8484
8574 77 1000 42 71 13 Returns: 733
Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysRain with a public method int getTime(int L, int D, int N, int P1, int M, int A) · 115 test cases · 2 s / 256 MB per case