2072 - GG

Enunț

Alex se află în sistemul de coordonate 2D. Aflându-se în coordonatele (x, y), el primește un număr aleator între 1 și 2 (50% șanse să primească 1 și 50% șanse să primească 2). Dacă acest număr este 1, atunci el se va deplasa în (x + 1, y), altfel în (x, y + 1).

Cerința

Știind că Alex pornește (1, 1), se întreabă care este probabilitatea ca acesta să treacă prin (N, M).

Date de intrare

Programul citește de la tastatură numerele N și M.

Date de ieșire

Programul va afișa pe ecran numărul P, reprezentând probabilitatea cerută.

Restricții și precizări

• 1 ≤ N, M ≤ 100000

Exemplul 1

Input:

2 3

Output:

0.375

Exemplul 2

Input:

99999999999999 2

Output:

Restrictiile nu sunt indeplinite.

Rezolvare

def check_restrictions(N, M):
    return 1 <= N <= 100000 and 1 <= M <= 100000

def calculate_probability(N, M):
    MOD = 10**9 + 7

    dp = [[0.0] * (M + 1) for _ in range(N + 1)]

    dp[1][1] = 1.0  # Probabilitatea inițială

    for i in range(1, N + 1):
        for j in range(1, M + 1):
            if i < N:
                dp[i + 1][j] += 0.5 * dp[i][j]
            if j < M:
                dp[i][j + 1] += 0.5 * dp[i][j]

    return dp[N][M]

if __name__ == "__main__":
    N = int(input("Introduceti valoarea pentru N: "))
    M = int(input("Introduceti valoarea pentru M: "))

    if not check_restrictions(N, M):
        print("Restrictiile nu sunt indeplinite.")
    else:
        result = calculate_probability(N, M)
        print(f'{result:.3f}')