Problem : Water Management There are N tubs of water, numbered from 1 to N. Initially there is a few litres of water in each tub. Each water tub has 2 taps attached to it. Incoming Tap with speed x litres / second and Outgoing Tap with speed y litres / second. Let water(i) denote the final volume of water in ith tub. Amit wants to attain such a situation that water(i) < water(i+1) for 1<=i <=N. i.e. water in each tub must be less than water in the tub next to it. He wants to do this as quickly as possible. You task is to find out and tell Amit, what is the minimum number of seconds required to attain in this situation.
Input Format: First line will contains the number of tubs, denoted by N Next N lines contain a tuple with 3 integers delimited by white space. The tuple contents are
Wi - volume of water present initially in ith tub (in litres)
x - speed of incoming tap of ith tub ( in litres/second)
y - speed of outgoing tap of ith tub ( in litres/second)
Output Format: Minimum time in seconds, needed to arrange water in N tubs, in ascending order of volume.
Constraints: 2 <= N <= 100000 0 <= W <= 1000000000 (1 billion) for each tub 1 <= x <= 10000 for each tub 1 <= y <= 10000 for each tub A tap can be used only for integral number of seconds i.e. you cannot use a tap for 0.3 or 0.5 seconds. It can be used either for 1,2,3… Seconds Capacity of each tub is infinite. Volume of water in any tub cannot be less than zero at any point of time. Any number of taps can be turned on or off simultaneously. Sample Input and Output
Explanation for sample input and output 1: Here we have 3 tubs with following information about each of them
Tub Number Initial Volume Incoming Tap speed Outgoing Tap speed Tub 1 2 3 3 Tub 2 3 4 5 Tub 3 3 5 5
Initially tub 2 and 3 have same volume of water. So he will just turn on the Incoming Tap at Tub 3 for one second. After one second the water in 3rd tub will be 8 litres. Since 2 < 3 < 8, the answer is 1 second.
Explanation for sample input and output 2: Here we have 3 tubs with following information about each of them
Tub Number Initial Volume Incoming Tap speed Outgoing Tap speed Tub 1 6 2 1 Tub 2 4 1 3 Tub 3 4 1 4
As we can see that it is impossible to do the task in one second. But it can be done in two second as below. Turn on the outgoing tap at tub 1. So after two seconds water level will reduce to 4 litres. Turn on the incoming tap at tub 2 only for one second. So water level will be 5 litres. Turn on the incoming tap at tub 3 for two seconds. So water level will be 6 litres. Since 4 < 5 < 6, the answer is 2 seconds.