Solution to the problem B of Round1B of CodeJam: https://code.google.com/codejam/contest/2434486/dashboard#s=p1

diamonds.rb

# 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