Skip to content

Instantly share code, notes, and snippets.

@dashohoxha
Created May 4, 2013 23:32
Show Gist options
  • Save dashohoxha/5519146 to your computer and use it in GitHub Desktop.
Save dashohoxha/5519146 to your computer and use it in GitHub Desktop.
Solution to the problem B of Round1B of CodeJam: https://code.google.com/codejam/contest/2434486/dashboard#s=p1
# Solution to the problem B of Round1B of CodeJam:
# https://code.google.com/codejam/contest/2434486/dashboard#s=p1
# Number of diamonds on a piramid of 'i' full layers.
def f(i)
2*i*i + 3*i + 1
end
# Find the layers of the full piramid.
def find_i(n)
l = 0
h = 1
while f(h) <= n
l = h
h = 2*h
end
while l < h-1
m = (l+h)/2
if f(m) <= n
l = m
else
h = m-1
end
end
return l
end
# The probability of having 'k' heads in 'n' coin tosses.
def binomial_prob(n, k)
return 1.0/(2**n) if n==k
denom = 1
for i in 1 .. (n-k)
denom *= i
end
enum = 1
for i in (k+1) .. n
enum *= i
end
p = (enum.to_f / denom) * (0.5**n)
return p
end
# Calculate the probability that out of 'n' drops,
# at least 'k' fall on one side.
def prob(n, k, i)
return 0.0 if k > n
side_length = 2*i + 2
p = binomial_prob(n, k)
sum = p
i = k
while i < n and i < side_length
i += 1
p = p * (n - i + 1) / i
sum += p
end
return sum
end
def solve(n, x, y)
i = find_i(n)
return 1.0 if y < 2*(i+1) - x.abs
return 0.0 if y > 2*(i+1) - x.abs
return 0.0 if x.zero?
n1 = n - f(i)
return 0.0 if n1.zero?
k = 2*i + 3 - x.abs
return prob(n1, k, i)
end
T = gets.to_i
for t in 1..T
n, x, y = gets.chomp.split.map { |x| x.to_i }
p = solve(n, x, y)
puts "Case ##{t}: #{p}"
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment