1257 - NumarParanteze
Cerința[edit | edit source]
Să se determine numărul de șiruri de lungime 2 * n care conțin paranteze închise corect.
Date de intrare[edit | edit source]
Programul citește de la tastatură numărul n.
Date de ieșire[edit | edit source]
Programul va afișa pe ecran restul împărțirii numărului de șiruri de lungime 2 * n, care sunt parantezate corect, la 666013.
Restricții și precizări[edit | edit source]
- 1 ≤ n ≤ 1000
Exemplu[edit | edit source]
- Intrare
3
- Ieșire
5
Explicație[edit | edit source]
((())), ()(()), ()()(), (())(), (()()).
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line=""> def numar_siruri_parantezate_corect(n):
MOD = 666013 dp = [0] * (n + 1) dp[0] = 1
for i in range(1, n + 1):
for j in range(i):
dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % MOD
return dp[n]
- Citire date de intrare
n = int(input("Introduceți n: "))
- Calcul și afișare rezultat
rezultat = numar_siruri_parantezate_corect(n) print(rezultat) </syntaxhighlight>