Pentru a construi
expresii matematice, folosim in practica trei tipuri de paranteze: "(" si ")",
"[" si "]", "{" si "}". Un sir de caractere (format doar din cele 6 paranteze
de mai sus) este corect parantezat daca si numai daca parantezele sunt imbricate
corect si, in plus:
- intre oricare doua paranteze rotunde aflate in corespondenta nu apar paranteze patrate sau
acolade;
- intre oricare doua paranteze patrate aflate in corespondenta nu apar acolade.
Pentru rezolvitorii
cu inclinatii matematice (ceilalti pot sari cu incredere peste aceasta descriere
matematica plictisitoare), putem reformula conditia de parantezare corecta astfel:
Fie s un sir de caractere format
doar din cele 6 paranteze de mai sus. Notam cu a[i][c]
numarul de caractere c aflate
in prefixul de lungime i al lui
s. s
este o parantezare corecta daca si numai daca pentru orice 1<=i<=N:
- a[i]['('] - a[i][')']
>= 0 si a[i]['['] - a[i][']'] >= 0 si a[i]['{'] - a[i]['}'] >= 0
- (a[i]['('] - a[i][')'] > 0) ==> ((a[i]['['] - a[i][']'] = 0) si (a[i]['{']
- a[i]['}'] = 0))
- (a[i]['['] - a[i][']'] > 0) ==> (a[i]['{'] - a[i]['}'] = 0)
Un exemplu de
sir corect parantezat este "[[]()]{}".
Sirul "())(" nu este parantezat
corect deoarece parantezele nu sunt imbricate corect. Sirul "([])"
nu este parantezat corect deoarece []
apare in interiorul unor paranteze rotunde.
Cerinta
Sa se determine cate siruri de parantezari corecte de lungime N
exista.
Date de
intrare Pe
prima linie a fisierului parent.in
se gaseste numarul natural N.
Date de
iesire Pe
singura linie a fisierului parent.out
afisati numarul calculat, modulo 9311.