1257 - NumarParanteze

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

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

1. Citire date de intrare

n = int(input("Introduceți n: "))

1. Calcul și afișare rezultat

rezultat = numar_siruri_parantezate_corect(n) print(rezultat) </syntaxhighlight>