ZOJ Problem Set - 3464
CM is a member of Rugby football club of ZJU. He loves to play the game. Every Friday afternoon there is a club training of skills. CM wants to make it more effective.
In the training, N club members including CM stand at staring line in a row. The maximum velocity of the ith player is Vi. The distance between the line and touchdown zone is L. The goal is to send the ball to touchdown zone. They can pass the ball to others but forward passing is illegal. If someone reaches touchdown zone with ball, the team scores and it will be an effective training.
This picture illustrate the rule of passing ball.
But the way to scoring is not easy because of crazy opponents. Any player with the ball cannot rush more than T seconds or he will be tackled. And he cannot be passed again because he will be very tired after sprinting; even have not for T seconds enough. At the beginning CM can choose who takes the ball first. Now CM wants to know whether they can score and how fast they can.
The first line is an integer RP. Then RP cases follow. There are no more than 20 cases.
For each case, there are two lines. The first line contains three integers N, T, L (1 ≤ N,T ≤ 10000, 1 ≤ L ≤ 109). The second line has N integers indicating V1, V2 ... Vn. (1 ≤ Vi ≤ 10000)
A single line with a float number S and correct to two decimal places. It means the total seconds they need to score. If they cannot score, output -1.
2 3 4 20 2 3 4 1 1 10 2
Author: HUANG, Minzhi
Contest: ZOJ Monthly, January 2011