WaterTank
SRM 676 · 2015-11-03 · by lg5293
Problem Statement
You are given the
At time 0 water will start flowing into the tank through an input pipe. This process will consist of n consecutive intervals, numbered 0 to n-1 in order. Interval i lasts for t[i] seconds. During each second of interval i exactly x[i] liters of water will enter the tank.
The tank also has an output pipe. The water will always leave the tank through the output pipe as quickly as it can. The output pipe has a valve. You can use the valve to set the output pipe to any maximum output rate R (in liters per second). This maximum output rate must remain constant during the entire process. The rate must be nonnegative but it doesn't have to be an integer.
Determine and return the smallest output rate limit R such that the amount of water in the tank will never exceed C liters.
Notes
- Your return value must have an absolute or relative error smaller than 1e-6.
Constraints
- n will be between 1 and 50, inclusive.
- t,x will have exactly n elements.
- Each element of t will be between 1 and 1,000,000, inclusive.
- Each element of x will be between 1 and 1,000,000, inclusive.
- C will be between 1 and 10^9, inclusive.
{3,3}
{1,2}
3
Returns: 0.9999999999999999
In this case, we have two time intervals, the first one lasts 3 seconds and water flows at 1 liter per second. The second one lasts 3 seconds and water flows in at 2 liters per second. The answer in this case is 1. During the first interval, water flows in and out at the same rate, while in the second interval, water flows in at a net rate of 1 liter per second. Any lower output rate would cause the tank to overflow 3 liters.
{1,2,3,4,5}
{5,4,3,2,1}
10
Returns: 1.9999999999999996
{5949,3198,376,3592,4019,3481,5609,3840,6092,4059}
{29,38,96,84,10,2,39,27,76,94}
1000000000
Returns: 0.0
{9,3,4,8,1,2,5,7,6}
{123,456,789,1011,1213,1415,1617,1819,2021}
11
Returns: 2019.1666666666665
{100}
{1000}
12345
Returns: 876.55
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WaterTank with a public method double minOutputRate(vector<int> t, vector<int> x, int C) · 90 test cases · 2 s / 256 MB per case