[题解]Let’s Celebrate the 100th Contest on ZOJ! » ZOJ3445quark

ZOJ3445quark
ZOJ3445quark.py


import sys
import math

base, eps, factorial = 10 ** 106, 10 ** 69, [math.factorial(x) for x in range(0, 101)]
base2 = base * base

def binomial(n, i):
	return factorial[n] / (factorial[n - i] * factorial[i])

def sqrt(x):
	r = long(math.sqrt(x))
	while True:
		l, r = r, (r + x / r) / 2
		if abs(l - r) <= eps:
			break
	return r

def gao(n):
	r = reduce(lambda p, q: p + q, [base2 / sqrt(binomial(n, i) * base2) for i in range(0, n + 1)])
	if str(r)[101] > '4':
		r += 1000000L
	s = str(r)
	return s[0] + '.' + s[1:101]

for n in sys.stdin:
	print(gao(long(n)))
Leave a Reply