Reservoir Tide Cycle
HardOnline Assessment
Track a tidal holding pond whose gate is operated on the same schedule every day, for a very long time.
The pond holds at most cap units of water and starts with start units. Every day the gate applies the same list events in order. A positive event e lets e units flow in; a negative event releases -e units.
- If an inflow would take the level above
cap, the pond ends atcapand the excess is lost (counted as overflow). - If a release would take the level below 0, the pond ends at 0 and the part that could not be released is the shortfall (counted).
- Clamping happens after each single event, not once per day.
Report the situation after days full days.
Input: cap, start, events, days.
Output: [level, lost, shortfall]: the water level after the last day, and the total overflow and total shortfall over all days days.
days can be as large as 10^12, so the days cannot be played out one at a time.
Example 1
- Input:
- [8,6,[5,-3,-4],4]
- Output:
- [0,3,5]
- Explanation
- cap 8, start 6, events +5, -3, -4 for 4 days. Day 1: 6 + 5 = 11 exceeds 8 so 3 is lost and the level is 8; then 5, then 1. Day 2: 1 + 5 = 6, 3, then -4 would give -1, so the shortfall is 1 and the level is 0. Days 3 and 4 each go 5, 2, then a shortfall of 2. The final level is 0, with 3 lost and 1 + 2 + 2 = 5 short.
Example 2
- Input:
- [20,3,[7,-2,-2],6]
- Output:
- [16,5,0]
- Explanation
- cap 20, start 3, events +7, -2, -2 for 6 days. Each day without any clamping moves the level up by 3: 3, 6, 9, 12, 15, 18. On day 5 the start is 15, 15 + 7 = 22 overflows by 2 and the level ends the day at 16; on day 6 the start is 16, 16 + 7 = 23 overflows by 3 and it ends at 16 again. Total lost 5, final level 16.
Example 3
- Input:
- [1000000000000,0,[7,-2,-3],1000000000000]
- Output:
- [999999999995,1000000000005,0]
- Explanation
- cap 1012, start 0, events +7, -2, -3 for 1012 days. The level rises by 2 every day, and nothing is clamped while the start is at most cap - 7, which holds for the first 499,999,999,997 days. Then the start is 999,999,999,994: one unit overflows and the day ends at 999,999,999,995. From then on every day starts at 999,999,999,995, overflows by 2 and ends where it began. Counting these repeated days with one multiplication gives final level 999,999,999,995 and total lost 1,000,000,000,005.
Constraints
- 1 ≤ cap ≤ 1012; 0 ≤ start ≤ cap
- 1 ≤ events.length ≤ 40; events[i] ≠ 0; |events[i]| ≤ 100
- 0 ≤ days ≤ 1012