Fişierul intrare/ieşire: | brackets2.in, brackets2.out | Sursă | ACM-ICPC Faza Nationala 2018 |
Autor | Mihai Calancea | Adăugată de | |
Timp execuţie pe test | 0.25 sec | Limită de memorie | 524288 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Brackets2
Ajungi la laboratorul de algoritmi. Nimeni nu spune nimic. Laborantul e cu picioarele pe masă, cu ochelarii de soare pe ochi şi se uită melancolic pe fereastră. E clar că e venit din club şi încearcă să compună o temă de laborator pe moment. În final, spune:
Se dă o secvenţă de N paranteze. În câte feluri se pot alege două subsecvenţe disjuncte şi nevide, A şi B, A la stânga lui B, astfel încât sirul obtinut prin concatenarea şirului A cu şirul B constituie o parantezare corectă?
O parantezare corectă este definită astfel:
- Şirul vid este corect.
- Daca şirul A este corect, atunci şi şirul (A) este corect.
- Daca şirurile A si B sunt corecte, atunci şi şirul A concatenat cu B este corect.
Date de intrare
Fişierul de intrare brackets2.in conţine pe prima linie, numărul T de teste. Pe următoarele T linii se află câte un şir de paranteze.
Date de ieşire
În fişierul de ieşire brackets2.out se află T linii, pe fiecare aflându-se un număr egal cu răspunsul la întrebarea din enunt pentru şirul corespunzător.
Restricţii
- 1 ≤ T ≤ 25
- 1 ≤ N ≤ 1.500
- Pentru cel putin 18 teste, 1 ≤ N ≤ 100
- O subsecvenţă a unui şir este un subşir de elemente consecutive ale acestuia.
Exemplu
brackets2.in | brackets2.out |
---|---|
1 (()) | 7 |