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)
        if time_if_wait <= time_if_buy:
            return time + time_if_wait
        time += C / rate
        rate += F
Advertisements

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. 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;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s