Created
May 4, 2013 23:32
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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