beecrowd | 2030

Pit Stop

By Daniel Saad, Instituto Federal de Goiás BR Brazil

Timelimit: 1

“Grazie, grazie, bellissimo!” – said a engineer of Scuderia Ferrari after an unexpected strategy which made then win the Formosa GP of 2016, famous street circuit of the Formula One calendar.

Formula One is a bit crazy sport. Sometimes, when the tyre is worn, it is worth to make a pit stop in order to put new tyres and do faster laps.

However, it is not always that making a pit stop translates into an advantage. It depends of the quantity of remaining laps and the pit stop time.

The tyres have a life span of few laps until being worn. Then, possibly a pit stop could be necessary in order to gain time with fresh tyres.

Are you capable of calculating the optimal strategy as a future Ferrari engineer?


The input consists of a line containing a number N (1 ≤ N ≤ 1000) indicating the number of test cases. The following N lines represent a test case. Each test case is composed by five integers:


Each test case output must begin with the line “Teste #i”, indicating the test case number. After this, a new line should give the least time possible (sum of the time of each lap and pit stop) of the optimal strategy to complete the Formosa GP and the minimum number of pit stops possibles to minimize this time. These two information must be separated by a space.

After each test case, a blank line must be printed.

Input Sample Output Sample

110000 113000 20000 15 70
110000 113000 20000 20 15
110000 112000 20000 15 70

Teste #1
7780000 4

Teste #2
1650000 0

Teste #3
7780000 3