Fişierul intrare/ieşire:parentrises.in, parentrises.outSursăBOI 2018
AutorAndrei Constantinescu, Bogdan CiobanuAdăugată deAndrei1998Andrei Constantinescu Andrei1998
Timp execuţie pe test0.3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Parentrises

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 + printre caracterele stringului. De exemplu, stringurile ()() şi (()) sunt bine parantezezate, căci pot fi transformate în +(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?

Date de intrare

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.

Date de ieşire

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.

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

Exemple

parentrises.inparentrises.out
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ă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?