Cookie Farm
InterviewTime limit10sMemory limit64 MB
You start at rate 2 and buy farms to reach X cookies in the least total time.
Problem
Cookie Farm is a clicker game. Players click a picture of a giant cookie to earn cookies, then spend those cookies on buildings that make cookies arrive faster.
In this problem you start with 0 cookies and earn 2 cookies per second by clicking the giant cookie. Whenever you hold at least cookies you can buy one cookie farm. Each farm costs cookies and permanently adds cookies per second to your production.
You win the moment you hold cookies that you have not spent on farms. Write a program that finds how long winning takes under the best possible strategy.
Cookies arrive continuously. seconds after the game starts you have cookies, and seconds after it starts you have cookies.
For , and the best strategy plays out like this.
- You start with 0 cookies and a production of 2 cookies per second.
- After seconds you hold cookies, so you buy a farm that adds cookies per second.
- After the purchase you hold 0 cookies and your total production is 6 cookies per second.
- The next farm also costs 500 cookies, which you can afford about seconds later.
- After the second purchase you hold 0 cookies and your total production is 10 cookies per second.
- The farm after that also costs 500 cookies, which you can afford seconds later.
- After the third purchase you hold 0 cookies and your total production is 14 cookies per second.
- A fourth farm would also cost 500 cookies, but skipping it is better. Waiting instead until you hold cookies takes about seconds.
The total is seconds.
Input
The first line contains the number of test cases ().
Each of the next lines contains three space-separated real numbers , and , with the meanings given above.
, , .
Each of , and is written as one or more digits, then a single decimal point, then 1 to 5 digits. No value has a leading zero.
Output
For each test case print one line of the form Case #x: y, where is the test case number starting from 1 and is the minimum number of seconds before you hold cookies.
Round to four decimal places and print exactly four digits after the decimal point.