## Wednesday, April 16, 2014

### Example

Suppose C=500.0, F=4.0 and X=2000.0. Here's how the best possible strategy plays out:
2. After 250 seconds, you will have C=500 cookies and can buy a farm that producesF=4 cookies per second.
3. After buying the farm, you have 0 cookies, and your total cookie production is 6 cookies per second.
4. The next farm will cost 500 cookies, which you can buy after about 83.3333333seconds.
5. After buying your second farm, you have 0 cookies, and your total cookie production is 10 cookies per second.
6. Another farm will cost 500 cookies, which you can buy after 50 seconds.
7. After buying your third farm, you have 0 cookies, and your total cookie production is 14 cookies per second.
8. 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.

### [代码]

 public class CookieClickerAlpha { public static void main(String[] args) { Scanner scanIn = new Scanner(System.in); int testCaseNum = scanIn.nextInt(); int iter = 1; while (iter <= testCaseNum) { double c = scanIn.nextDouble(); double f = scanIn.nextDouble(); double x = scanIn.nextDouble(); double result = leastTime(c, f, x); System.out.println(String.format("Case #%d: %.7f", iter, result)); iter++; } scanIn.close(); } public static double leastTime(double c, double f, double x) { double currentSpeed = 2; double total = 0.0; double orig = 0; double nextTime = 0; while(true) { orig = x / currentSpeed; nextTime = c / currentSpeed + x / (currentSpeed + f); if (orig < nextTime) break; // keep buying farm total += c / currentSpeed; currentSpeed += f; } total += x / currentSpeed; return total; }

### [测试]

Input
Output
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

### [Reference]

1. 感谢水中的鱼对包子的帮助，Blog:http://fisherlei.blogspot.com/