Cookie Clicker: Google Code Jam 2014

[题目]

这道题目是Google Code Jam 2014年的题目B，来自于一个很有意思的小网页游戏，cookie clicker (http://orteil.dashnet.org/cookieclicker/)，题目的链接在这里(https://code.google.com/codejam/contest/dashboard?c=2974486#s=p1)，有兴趣可以读完，但是除去故事和润色的部分，题目的本质就是，你一开始有0块饼干，饼干每秒钟增长两个，当你有C（e.g.,500）个饼干的时候，你就可以买一个农场，好处是你每秒钟可以得到2+F(e.g., 4) 个饼干。你的goal是用最少的时间得到X(e.g., 2000)个饼干。

Example

Suppose C=500.0, F=4.0 and X=2000.0. Here's how the best possible strategy plays out:

1. You start with 0 cookies, but producing 2 cookies per second.
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.

[澄清]

因为是比赛的题目，所以需要注意的地方已经被写得很清楚了。需要注意的是例子最后的一句话，饼干是可以连续的。

[思路]

乍一看来一个想法就是写出递推函数, 如果不买农场的话，f(t) = X / 2,如果买一个农场的话， f(t) = C / 2 + X / (2 + F) , 如果买两个的话。。。以此类推。然后对于这个函数求导数，就可以得到时间。但是事实上并没有那么复杂，因为这道题目的目标是最快的达到目标，得到饼干的速度只会增不会减，所以只需要比较当前的速度到达目标和买一个农场之后的速度到达目标的时间比较一下即可，贪心算法。

[代码]

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/