Submission #188395

---

Source Code Expand

#!/usr/bin/env python2.7

import sys
from collections import namedtuple

from cStringIO import StringIO
import unittest
import cProfile

def main():
    N, D = (int(x) for x in sys.stdin.readline().split())
    X, Y = (int(x) for x in sys.stdin.readline().split())
    print solve(N, D, X, Y)

cc = [[1]]
for i in xrange(1,1001):
    ccl = [1]
    for j in xrange(1,i):
        ccl.append(cc[-1][j-1] + cc[-1][j])
    ccl.append(1)
    cc.append(ccl)

def comb(A, B):
    return cc[A][B]

def count(a, b, c, d):
    P = (a, b, c, d)
    N = sum(P)
    return comb(N, a) * comb(N - a, b) * comb(N - a - b, c)

def subsolve(N, X, Y):
    X = abs(X)
    Y = abs(Y)
    R = N - X - Y
    if R % 2 != 0:
        return 0
    R /= 2

    res = 0
    for rx in xrange(R+1):
        ry = R - rx
        res += count(X+rx, rx, Y+ry, ry)

    D = 10 ** 11
    return float((res * D) / (4 ** N)) / D

def solve(N, D, X, Y):
    if X % D != 0 or Y % D != 0:
        return 0

    return subsolve(N, X / D, Y / D)
    
class Test(unittest.TestCase):

    @staticmethod
    def tryone(indata):
        sys.stdin = StringIO(indata)
        out = sys.stdout = StringIO()
        main()
        return out.getvalue()

    def test20(self):
        self.assertEqual(comb(0,0), 1)
        self.assertEqual(comb(1,0), 1)
        self.assertEqual(comb(1,1), 1)
        self.assertEqual(comb(2,0), 1)
        self.assertEqual(comb(2,1), 2)
        self.assertEqual(comb(2,2), 1)
        self.assertEqual(comb(3,0), 1)
        self.assertEqual(comb(3,1), 3)
        self.assertEqual(comb(3,2), 3)
        self.assertEqual(comb(3,3), 1)

    def test50(self):
        self.assertAlmostEqual(solve(2, 10000000, 10000000, 10000000), 0.125)
        self.assertAlmostEqual(solve(100, 2, 3, 7), 0)
        self.assertAlmostEqual(solve(11, 8562174, 25686522, 17124348), 0.018174648284912)

    def test80(self):
        L = 123456789
        solve(1000, L, 0, 0)

    def test90(self):
        self.assertEqual(self.tryone("""\
2 10000000
10000000 10000000
"""), """0.125\n""")

if __name__ == '__main__':
    if len(sys.argv) > 1:
        print "_/" * 30 + str(sys.argv)
        if sys.argv[1] == '-p':
            sys.argv.pop(1)
            cProfile.run("unittest.main(exit=False, failfast=True)", sort='time')
        else:
            unittest.main()
    else:
        main()

Submission Info

Judge Result