Fişierul intrare/ieşire:brackets2.in, brackets2.outSursăACM-ICPC Faza Nationala 2018
AutorMihai CalanceaAdăugată de
Timp execuţie pe test0.5 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 ş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.inbrackets2.out
1
(())
7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?