This problem was created by Clive Fraser aka CSFPython - many thanks!
One morning farmer Giles said to his three children (Alan, Barbara and Claude) that their horse Dobbin was no longer of much use on their farm and that Dobbin was going to be transferred to their Uncle Joe's farm; where he would be of some use. Farmer Giles said that he would like one of the children to take Dobbin to Uncle Joe's farm. The three children all wanted to see Uncle Joe and all three really enjoy the journey on the track over the moors to his farm. It was decided that all three would go.
Unfortunately the children do not like travelling together because they each prefer going at their own speed. They decided on a plan to get to Uncle Joe's with Dobbin, in the shortest possible time. Dobbin, being a horse, cannot make progress on the journey unless he is accompanied by one of the children. The child can ride Dobbin, in which case they go at Dobbin's speed. If the child walks with Dobbin then the pair go at the slower speed of the two. It is not necessary for the same child to take Dobbin over the whole distance. Dobbin can be transferred between children at any point on the journey where children meet. It is also possible for the child with Dobbin to tether the horse at the side of the track and then to leave him there until one of the other children arrives to pick him up. For simplicity we will assume that the times to transfer Dobbin between children and the times taken to tether and untether the horse can all be neglected.
Dobbin and each of the children maintain their preferred speeds at all times except for the following: Dobbin is stationary when tethered at the side of the track. When a child is walking with Dobbin they both travel at the slower speed of the two. A child riding on Dobbin goes at Dobbin's speed. Some of the speeds are typical of jogging speeds rather than walking speeds. This is not unusual because many hill farmers are very fit people who can maintain a good jogging pace for several hours.
Your task is to find the minimum possible time for the three children and Dobbin to travel to Uncle Joe's. They do not have to leave home at the same time and they do not need to arrive at the same time at Uncle Joe's. The time taken will be measured from the time when the first child leaves home to the time when the last child reaches Uncle Joe's; with the extra condition that Dobbin must have arrived with one of the children. The distance from home to Uncle Joe's is exactly 30 km. The four speeds are given in kilometres per hour. The journey time is to be calculated in seconds and should be rounded to the nearest second. It is guaranteed that the exact time for the fastest journey will be not more than 0.3 seconds from the nearest whole second.
Input and Answer
The first line of the problem will be a single integer N denoting the number of test cases. Each of the
following N lines will hold 4 separate values (each). These are the speeds of Alan, Barbara, Claude
and Dobbin, in that order. For each test case you must find the fastest journey time (to the nearest second).
Give these answers, separated by spaces, as a single string.
Example:
input:
2
7.986 5.413 10.588 6.739
5.437 7.603 6.958 10.764
answer:
16026 13853