puzzle #2

gistfile1.py

import sys
import math

# yes, stolen from wikipedia.
def binomialCoefficient(n, k):
	if k < 0 or k > n:
		return 0
	if k > n - k: # take advantage of symmetry
		k = n - k
	c = 1
	for i in range(k):
		c = c * (n - (k - (i+1)))
		c = c // (i+1)
	return c

def hypergeometric(N, m, n, k):
	a = binomialCoefficient(m, k)
	b = binomialCoefficient(N-m, n-k)
	c = binomialCoefficient(N, n)
	return a * b * 1.0 / c

if __name__ == '__main__':
	m, n, t, p = [int(x) for x in sys.stdin.readline().split()]

	# how many of our friends must win?
	w = int(math.ceil(p * 1.0 / t)) if p > t else 1

	# hypergeometric distribution
	pr = sum(hypergeometric(m, p, n, i) for i in xrange(w, p+1))
	print '%.10f' % pr