== include(page="template/taskheader" task_id="parentrises") ==
Poveste şi cerinţă...
Definim un string ca o secvenţă de caractere $($ şi $)$.
Definim un string bine paratezat ca un string care poate fi transformat într-o expresie aritmetică corectă prin inserarea caracterelor $1$ şi <tex>+</tex> printre caracterele stringului. De exemplu, stringurile $()()$ şi $(())$ sunt bine parantezezate, căci pot fi transformate în $(1)+(1)$ şi $((1+1)+1)$ respectiv. Pe de altă parte, $)($ şi $($ nu sunt bine parantezate. Convenim că stringul vid este bine parantezat.
Bogdan Păcuraru şi Costel Rostogolitul lucreaza la B.P.A.N. (Biroul Problemelor Algoritmice Nenecesare), divizia paranteze inutile. Ei primesc două tipuri de sarcini:
* Teo al Focului şi Radu Muntele (clienţii lor), ambii daltonişti, au un string $S$. Teo poate vedea doar roşu şi verde, pe când Radu poate vedea doar albastru şi verde. Ei vor să coloreze $S$ folosind culorile roşu, verde şi albastru astfel încât amândoi vor vedea un string bine parantezat daca ignoră parantezele cu culori pe care nu le pot vedea. Dacă o astfel de colorare există, spunem că $S$ este $RGB-citibilă$. Găseşte o colorare, sau indică ca nu există.
* Mihai Precumlancea şi Andrei Preotul (alţi clienţi) vor să ştie câte şiruri $RGB-citibile$ de lungime $N$ există, pentru un $N$ dat. Vor răspunsul modulo $1.000.000.007$.
Bogdan şi Costel deobicei rezolvă aceste sarcini cu ajutorul limbajelor C / C++, dar Bunelul cel Rău le-a spart calculatoarele şi ei pot folosi doar Rust. Din nefericire, ei nu cunosc nimic despre Rust; îi poţi ajuta?
h2. Date de intrare
Fişierul de intrare $parentrises.in$ ...
Prima linie a fişierului de intrare $parentrises.in$ va conţine un număr $P$, ce denotă tipul de sarcină pe care o vei rezolva:
* Dacă $P = 1$, vei rezolva sarcina dată de Teo şi Radu
* Dacă $P = 2$, vei rezolva sarcina dată de Mihai şi Andrei.
A două linie va conţine un număr $T$, ce reprezintă numărul de teste din fişier. Vor urma cele $T$ teste, câte unul pe un rând:
* Dacă $P = 1$, un test va conţine stringul $S$.
* Dacă $P = 2$, un test va conţine numărul $N$.
h2. Date de ieşire
În fişierul de ieşire $parentrises.out$ ...
Fişierul de ieşire $parentrises.out$ va conţine răspunsurile pentru cele $T$ teste, câte unul pe un rând.
Dacă $P = 1$ şi nu există soluţie, se afişează $impossible$.
Dacă $P = 1$ şi există soluţie, printează o colorare posibilă. Cel de al $i$-lea caracter pe linie va reprezenta culoarea celui de al $i$-lea caracter din $S$: $R$ reprezinta roşu, $B$ reprezintă albastru şi $G$ reprezinta verde.
Dacă $P = 2$, afişează câte şiruri $RGB-citibile$ de lungime $N$ există, modulo $1.000.000.007$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* Pentru $5$ puncte, $P = 1, 1 ≤ T ≤ 5, 1 ≤$ lungimea lui $S$ $≤ 13$
* Dacă $L$ este suma lungimilor stringurilor din input, atunci pentru alte $11$ puncte, $P = 1, 1 ≤ L ≤ 100$
* Pentru alte $6$ puncte, $P = 1, 1 ≤ L ≤ 1.000$
* Pentru alte $28$ puncte, $P = 1, 1 ≤ L ≤ 1.000.000$
* Pentru alte $6$ puncte, $P = 2, 1 ≤ N, T ≤ 15$
* Pentru alte $16$ puncte, $P = 2, 1 ≤ N, T ≤ 30$
* Pentru alte $28$ puncte, $P = 2, 1 ≤ N, T ≤ 300$
h2. Exemplu
h2. Exemple
table(example). |_. parentrises.in |_. parentrises.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 1
3
())(()
()(()
()))
| GRBRBG
BBRBG
impossible
|
| 2
2
6
100
| 12
959772055
|
În primul test al primului fişier, atât Teo cât şi Radu vor vedea stringul $()()$.
În al doilea test al primului fişier, Teo va vedea stringul $()$, şi Radu va vedea stringul $()()$.
În al treilea test al primului fişier, nu există o colorare validă.
== include(page="template/taskfooter" task_id="parentrises") ==
