GCJ – Falling Diamonds

Falling Diamonds, Round 1B 2013

from scipy.stats import binom

def solve_case(case):
    """Take the input data (structured in case) and perform any necessary
    calculations to obtain the desired output, formatted as the appropriate
    string.
    """

    N, X, Y = case

    def hex(num):
        #hexagonal numbers
        return num * (2 * num - 1)

    #Figure out how many shells are filled
    maxshell = 710
    assert hex(maxshell + 1) > 1e6
    for n in xrange(maxshell):
        if N >= hex(n + 1):
            filled = n
            excess = N - hex(n + 1)
            size = hex(n + 2) - hex(n + 1)
        else:
            break
    assert excess < size

    shell = (abs(X) + abs(Y)) / 2

    if shell <= filled:
        #In a filled shell
        return 1.0
    elif shell > filled + 1:
        #In an empty shell
        return 0.0
    if X == 0:
        #At the peak of the partially filled shell
        return 0.0

    #Now we're in a partially filled shell
    up = abs(Y) #Number up from the bottom

    #See if we have enough to fill one whole side
    spilled = excess - (size - 1) / 2
    if spilled >= up + 1:
        return 1.0

    #Otherwise, just a binomial
    return 1 - binom.cdf(up, excess, 0.5)
Advertisements

One thought on “GCJ – Falling Diamonds

  1. Pingback: Google Code Jam – Summary | Reflections of Dusk

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