1257 - NumarParanteze
De la Universitas MediaWiki
Cerința
Să se determine numărul de șiruri de lungime 2 * n care conțin paranteze închise corect.
Date de intrare
Programul citește de la tastatură numărul n.
Date de ieșire
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
- 1 ≤ n ≤ 1000
Exemplu
- Intrare
3
- Ieșire
5
Explicație
((())), ()(()), ()()(), (())(), (()()).
Rezolvare
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)