| Fişierul intrare/ieşire: | paranteze3.in, paranteze3.out | Sursă | ad-hoc |
| Autor | Tudor Muresan | Adăugată de |  Ciprian Oprisa •cypry |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Paranteze inversate
Un şir conţinând numai paranteze de tipul '(' şi ')' este echilibrat în următoarele condiţii:
- şirul () este echilibrat;
- concatenarea a două şiruri echilibrate este un şir echilibrat;
- dacă s este un şir echilibrat, atunci (s) este un şir echilibrat.
Condiţia de echilibrare este mai "tare" decât faptul că numărul de paranteze '(' şi ')' este egal. De exemplu şirul '())(()' nu este echilibrat.
Sarcina voastră este de a reechilibra un şir de paranteze echilibrat, după ce o singură paranteză din şir este inversată. Mai exact, fiind dat un şir echilibrat şi după ce o paranteză la o poziţie specificată este inversată, trebuie inversată cea mai din stânga paranteză care reechilibrează şirul.
După ce şirul a fost modificat prin inversarea parantezei de la poziţia determinată de voi, operaţia continuă cu specificarea unei alte poziţii la care se inversează o paranteză, urmând ca voi să determinaţi din nou poziţia parantezie celei mai din stânga, a cărei inversare reechilibrează şirul.
Date de intrare
Fişierul de intrare paranteze3.in conţine mai multe exemple de test. Fiecare exemplu de test conţine pe prima linie numerele întregi N şi Q, separate de un spaţiu. Pe următoarea linie este dat şirul echilibrat s având lungimea N. Urmează o linie conţinând Q întregi qi ($1 ≤ qi ≤ N$) separaţi prin spaţiu, indicând poziţia parantezei inversate care dezechilibrează şirul. Fişierul se termină cu o linie care conţine 0.
Date de ieşire
Fişierul de ieşire paranteze3.out conţine pentru fiecare exemplu de test o singură linie care conţine Q întregi li separaţi prin spaţiu, reprezentând poziţia celei mai din stânga paranteze care reechilibrează şirul după inversarea parantezei qi.
Restricţii
- 2 ≤ N ≤ 10000
- 1 ≤ Q ≤ 5000
- fişierul de intrare conţine cel mult 20 de teste
Exemplu
| paranteze3.in | paranteze3.out |
|---|---|
| 6 3 ((())) 4 3 1 20 9 ()((((()))))()()()() 15 20 13 5 3 10 3 17 18 0 | 2 2 1 2 20 8 5 3 2 2 3 18 |
Explicaţie
În primul exemplu de test '((()))' se inversează paranteza 4 şi se reechilibrează inversând paranteza 2. La şirul rezultat '()(())' se inversează paranteza 3 şi se reechilibrează inversând paranteza 2. La rezultatul '(()())' se inversează paranteza 1 şi se reechilibrează inversând tot paranteza 1.
