A row of n open tanks stands on flat ground. Tank i (numbered 0..n-1 from left to right) has a flat floor at height 0 and width widths[i], so raising its water level by h takes widths[i] * h units of water. Between tank i - 1 and tank i there is a wall of height walls[i]; walls[0] is the outer wall on the left of tank 0 and walls[n] the outer wall on the right of tank n - 1. Walls are infinitely thin. All tanks start empty.
From time 0 on, each source (k, r) in sources pours r units of water per second into tank k. Return the water level of every tank at time t.
How water moves. At every moment the tanks are grouped into pools: maximal runs of adjacent tanks that share one water level L and where every wall inside the run has height at most L. (A single tank is a pool; initially every tank is its own pool at level 0.) The two walls at the ends of a pool are its boundary walls, and the lower of the two heights is its rim. A pool's level never exceeds its rim.
Water that arrives in a pool (from a source or from a neighbour) is handled like this:
- If the pool's level is below its rim, the water stays and raises the level: a pool of total width
Wreceivingqunits per second rises atq / Wper unit of time. - If the level equals the rim, the pool cannot hold more: all the arriving water flows over the boundary wall of rim height into the pool on the other side of that wall, where the same rules apply again. If both boundary walls have the rim height, the arriving water is split equally between the two sides. Water that flows over an outer wall leaves the system for good.
Whenever the water on both sides of a wall stands exactly at the height of that wall, the two pools join into one.
Return a list of n strings: the level of each tank at time t as an exact reduced fraction, written as an integer like "4" when it is whole and as "p/q" otherwise.
Examples
Input: widths = [1, 1, 1], walls = [10, 3, 5, 10], sources = [(0, 1)], t = 5
Output: ['3', '2', '0']
Explanation: tank 0 fills to its rim 3 at time 3; after that its water flows
over the wall into tank 1, which reaches height 2 at time 5.
Input: widths = [1, 1, 1], walls = [10, 3, 5, 10], sources = [(0, 1)], t = 7
Output: ['7/2', '7/2', '0']
Explanation: at time 6 tank 1 also stands at 3, the pools join and the pool
of width 2 rises at speed 1/2.
Constraints
1 <= n <= 60,1 <= widths[i] <= 20,1 <= walls[i] <= 10001 <= len(sources) <= 5,0 <= k < n,1 <= r <= 200 <= t <= 10**9
Goals
- Model a continuous process as a sequence of exact events
- Route flows through a chain of full pools, including equal splits
- Keep all quantities exact with fractions