In this problem, you start with 0 cookies. You gain cookies at a rate of 2 cookies per second, by clicking on a giant cookie. Any time you have at least C cookies, you can buy a cookie farm. Every time you buy a cookie farm, it costs you C cookies and gives you an extra F cookies per second.
Once you have X cookies that you haven’t spent on farms, you win! Figure out how long it will take you to win if you use the best possible strategy.
Suppose C=500.0, F=4.0 and X=2000.0. Here’s how the best possible strategy plays out:
- You start with 0 cookies, but producing 2 cookies per second.
- After 250 seconds, you will have C=500 cookies and can buy a farm that producesF=4 cookies per second.
- After buying the farm, you have 0 cookies, and your total cookie production is 6 cookies per second.
- The next farm will cost 500 cookies, which you can buy after about 83.3333333seconds.
- After buying your second farm, you have 0 cookies, and your total cookie production is 10 cookies per second.
- Another farm will cost 500 cookies, which you can buy after 50 seconds.
- After buying your third farm, you have 0 cookies, and your total cookie production is 14 cookies per second.
- Another farm would cost 500 cookies, but it actually makes sense not to buy it: instead you can just wait until you have X=2000 cookies, which takes about142.8571429 seconds.
Total time: 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762 seconds.
Notice that you get cookies continuously: so 0.1 seconds after the game starts you’ll have 0.2 cookies, and π seconds after the game starts you’ll have 2π cookies.
The first line of the input gives the number of test cases, T. T lines follow. Each line contains three space-separated real-valued numbers: C, F and X, whose meanings are described earlier in the problem statement.
C, F and X will each consist of at least 1 digit followed by 1 decimal point followed by from 1 to 5 digits. There will be no leading zeroes.
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the minimum number of seconds it takes before you can have X delicious cookies.
We recommend outputting y to 7 decimal places, but it is not required. y will be considered correct if it is close enough to the correct number: within an absolute or relative error of 10-6. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
1 ≤ T ≤ 100.
1 ≤ C ≤ 500.
1 ≤ F ≤ 4.
1 ≤ X ≤ 2000.
1 ≤ C ≤ 10000.
1 ≤ F ≤ 100.
1 ≤ X ≤ 100000.
4 30.0 1.0 2.0 30.0 2.0 100.0 30.50000 3.14159 1999.19990 500.0 4.0 2000.0
Case #1: 1.0000000 Case #2: 39.1666667 Case #3: 63.9680013 Case #4: 526.1904762
Cookie Clicker was created by Orteil. Orteil does not endorse and has no involvement with Google Code Jam.
购买的farm数量小于X / C，对于每一种情况算出其时间，然后挑选出最短时间即可。
std::cin >> T;
double C, F, X;
double t; // for Large input
for(int round = 1; round <= T; ++round)
std::cin >> C >> F >> X;
for(int farmNum = 0; farmNum < X / C; ++farmNum)
t[farmNum] = 0;
for(int i = 0; i < farmNum; ++i)
t[farmNum] += C / (2.0 + i * F);
t[farmNum] += X / (2.0 + farmNum * F);
double min = t;
for(int i = 1; i < X / C; ++i)
if(t[i] < min)
min = t[i];
std::cout << "Case #" << round << ": " << min << std::endl;