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

<syntaxhighlight lang="python3" line="1"> 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}')

</syntaxhighlight>