Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
Willy the spider used to live in the chemistry laboratory of Dr. Petro. He
used to wander about the lab pipes and sometimes inside empty ones. One night
while he was in a pipe, he fell asleep. The next morning, Dr. Petro came to
the lab. He didn't notice Willy while opening the valve to fill the pipes with
hot water. Meanwhile, Stanley the gray mouse got what was going to happen. No
time to lose! Stan ran hard to reach the valve before Willy gets drawn, but...
Alas! He couldn't make it!
Poor Willy was boiled in hot water, but his memory is still in our hearts. Though Stan tried his best, we want to write a program, in the memory of Willy, to compute the time Stan had, to rescue Willy, assuming he started to run just when the doctor opened the valve.
To simplify the problem, assume the pipes are all vertical cylinders with diameter 1 cm. Every pipe is open from the top and closed at the bottom. Some of the pipes are connected through special horizontal pipes named links. The links have very high flow capacity, but are so tiny that at any given time, the volume of water inside them is negligible. The water enters from top of one of the pipes with a constant rate of 0.25�� cm3/sec and begins to fill the pipe from the bottom until the water reaches a link through which it flows horizontally and begins to fill the connected pipe. From elementary physics we know if two pipes are connected and the surface of the water is above the connecting link, the level of water in both pipes remains the same when we try to fill one of them. In this case the water fills each pipe with a rate equal to half of the rate of incoming water. As an example, consider the following configuration:
First, the lower 2 centimeters of the left pipe is filled with water at full rate, then, the lower 3 centimeters of the right pipe is filled, and after that, the upper part of the two pipes are filled in parallel at half rate. The input to your program is a configuration of pipes and links, and a target level in one of the pipes (the heavy dotted line in the above figure). The program should report how long it takes for the level of water to reach the target level. For the above configuration, the output is 9 seconds.
It is assumed that the water falls very rapidly, such that the time required for the water to fall can be neglected. The target level is always assumed to be a bit higher than the specified level for it. As an example, if we set the target point to level 4 in the left pipe in the figure above, the elapsed time for water to reach that target is assumed to be 5 (not 2), Also note that if the water reaches to the top of a pipe (say in level x), it won't pour out outside the pipe until empty spaces in connected pipes below level x are filled (if can be filled, i.e. the level of water reaches the connecting links). (Note that there may be some links at level x, to which water is entered). After all such spaces are filled; the water level would not go up further.
The water enters into the first pipe.
No link crosses a pipe.
No two links have the same y coordinates.
No two pipes have the same upper-left x coordinates.
Both endpoints of each link are connected to pipes.