2072 - GG - Revision history

Miawinator: Pagină nouă: = 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
2023-12-16T14:15:15Z

Pagină nouă: = Enunț = Alex se află în sistemul de coordonate <code>2D</code>. Aflându-se în coordonatele <code>(x, y)</code>, el primește un număr aleator între <code>1</code> și <code>2</code> (<code>50%</code> șanse să primească <code>1</code> și <code>50%</code> șanse să primească <code>2</code>). Dacă acest număr este <code>1</code>, atunci el se va deplasa în <code>(x + 1, y)</code>, altfel în <code>(x, y + 1)</code>. = Cerința = Știind că Alex pornește <cod...

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

= Cerința =
Știind că Alex pornește <code>(1, 1)</code>, se întreabă care este probabilitatea ca acesta să treacă prin <code>(N, M)</code>.

= Date de intrare =
Programul citește de la tastatură numerele <code>N</code> și <code>M</code>.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>P</code>, reprezentând probabilitatea cerută.

= Restricții și precizări =

* <code>1 ≤ N, M ≤ 100000</code>

== 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>