Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-09-28 11:22:49.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:brackets2.in, brackets2.outSursăACM-ICPC Faza Nationala 2018
AutorMihai CalanceaAdăugată de
Timp execuţie pe test0.25 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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, A şi B, A la stânga lui B, astfel încât şirul A concatenat 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

Exemplu

brackets2.inbrackets2.out
1
(())
7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?