All submissions for this problem are available.
Pacific Club is organizing a boat race. Participants from all around the world has arrived to participate in this event. All participating team must have exactly 3 members to be eligible to take part in the race. Only a single shaft is provided to each team. The strength of participants differ to a great extent. Some participants can drive the boat at more speed than other using the shaft. Let say for a team T, one of the member M1 has ability to drive at speed C1, M2 can drive at speed C2, M3 can drive at speed C3. Distance traveled in unit time by team T is C1 when M1 has the shaft. M1 get exhausted after unit time and passes the shaft to one of the other team member and atleast C1 time units rest is required by him before he can take the shaft again. Hence a team member gets exhausted in one unit time and needs a rest of x unit time after his turn ( x is the speed capacity of that member ). Assuming that team members are intelligent, they schedule their turns such that they finish their race in least possible time, based on the capacities of team members.
1st line contains number of test cases.
1st line of each test case contains two integers, seperated by spaces, N D , where N=Number of teams, D= Distance to be covered.
1st line of each test case is followed by N lines, where ith line consist of three integers denoting the speed capacities of each team member of team i.
Output minimum amount of time taken by the teams that finished first (precision up to 2 decimal points) and list of all the team numbers of the team that finished first ( in increasing order ).
Speed capacity of each member will be within 1 to 20.
Input: 1 2 31 5 4 4 1 2 5 Output: 11.25 1
Explanation : Team 1's one of the optimum order would be : 4 4 5 X X 4 4 X 5 X 4 4
|Time Limit:||0.553333 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.