Submission #1674336

---

Source Code Expand

import numpy as np


def combi(l, r):
    if l == 0:
        return 0.0
    answer = 0.0
    for i in range(l, l - r, -1):
        answer += np.log(i)
    for i in range(r, 0, -1):
        answer -= np.log(i)
    return answer


def dfs(x, y, n):
    if n * D < abs(X - x) + abs(Y - y):
        return 0.0
    elif n * D == abs(X - x) + abs(Y - y):
        a = abs(X - x) // D
        b = abs(Y - y) // D
        return combi(n, a) + combi(n - a, b) + n * np.log(0.25)

    prob = 0.0
    result = np.zeros([4], np.float64)
    for i in range(4):
        if i == 0:
            result[i] = dfs(x + D, y, n - 1)
        elif i == 1:
            result[i] = dfs(x - D, y, n - 1)
        elif i == 2:
            result[i] = dfs(x, y + D, n - 1)
        else:
            result[i] = dfs(x, y - D, n - 1)
    for i in np.nonzero(result)[0]:
        if prob == 0.0 and result[i] != 0.0:
            prob = np.log(0.25) + result[i]
        elif result[i] != 0.0:
            result[i] += np.log(0.25)
            if result[i] > prob:
                prob = result[i] + np.log(np.exp(prob - result[i]) + 1.0)
            else:
                prob = prob + np.log(np.exp(result[i] - prob) + 1.0)
    return prob


N, D = [int(x) for x in input().split(' ')]
X, Y = [int(x) for x in input().split(' ')]

if abs(X) % D != 0 or abs(Y) % D != 0:
    print(0.0)
else:
    print(np.exp(dfs(0, 0, N)))

Submission Info

Judge Result