# GCJ – Cookie Clicker Alpha

Cookie Clicker Alpha, Qualification Round 2014.

This problem is also fairly simple, and we can solve it with a straightforward algorithm. Many thanks to both Dashamir and Karell who pointed out ways to simplify my original solution in the comments.

We want to decide for each farm if we’ll be able to win faster without buying the next farm (which will take $X / rate$ time) or with buying the next farm (which will take $C / rate$ time to save up cookies to buy the farm and a further $X / (rate + F)$ time to win with the new, higher, production rate. If we don’t buy the farm, we report the current time plus the time to win with the current rate. If we do buy the farm, then we just repeat the step above after incrementing our rate and time to account for the new farm purchase.

```def solve_case(case):
C, F, X = case

rate = 2.0
time = 0.0

while True:
time_if_wait = X / rate
time_if_buy = C / rate + X / (rate + F)
return time + time_if_wait
time += C / rate
rate += F
```

## 3 thoughts on “GCJ – Cookie Clicker Alpha”

1. I think that you don’t need to keep track of cookies, time and rate are the only things that matter.
This is my solution (in Ruby):

def get_time(c, f, x)
time = 0.0 # total time spent
r = 2.0 # rate of getting cookies
while true
t1 = x/r # time to win without rate increase
t2 = c/r + x/(r + f) # time to win with a rate increase
if t1 <= t2
return time + t1 # no need to increase the rate again
else # increate the rate once more
time += c/r
r += f
end
end
end

2. KarelI says:

Yes, the cookies var is not necessary because cookies = C is never read, thus it’s always zero and you can remove that.

You don’t have to “simulate” buying of the factory either, just calculate the total time and compare that to previous minimum. Other words – you calculate the same result X/rate twice in successive iterations. Here simpler solution:

double best = X / rate;
while (true) {
time += C / rate;
rate += F;
double act = time + X / rate;
if ( act > best )
break;
best = act;
}

3. You guys are absolutely right. I’ve updated the code to reflect your improvements. Thanks!