| Fişierul intrare/ieşire: | misakatelefon.in, misakatelefon.out | Sursă | AGM 2019, runda finala |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Misakatelefon
Misaka a inceput, de curand, sa joace un nou joc pe telefon. In acest joc, telefonul arata un sir nevid de caractere, care are lungimea initiala cel mult 1000. Asupra acestui sir, ea poate aplica urmatoarele operatii:
- Sa selecteze un substring pe care sa il stearga (abcd devine ad).
- Sa selecteze un substring pe care sa il dubleze (abcd devine abcbcd).
Dupa oricare operatie, sirul poate avea lungimea cel mult 1018.
Scopul jocului este sa generezi un al doilea sir de caractere, care are lungimea tot pana in 1000, folosind cel mult 1011 miscari. Ajutati-o pe Misaka sa castige, sau indicati ca acest lucru nu este posibil!
Date de intrare
Fişierul de intrare misakatelefon.in va contine T, numarul de teste in fisier.
Fiecare test va contine doua linii. Prima linie va contine sirul initial care apare pe ecranul lui Misaka; a doua linie va contine sirul final, care vrem sa-l generam.
Date de ieşire
În fişierul de ieşire misakatelefon.out se vor afisa raspunsurile pentru diversele teste, in ordine.
Pentru un test, daca nu exista solutie, se va afisa numarul -1. Altfel, afisati un numar Q, ce reprezinta numarul de operatii pe care il folositi. Afisati apoi Q linii, fiecare fiind de forma t l r, cu semnificatia: eliminati (daca t = 0) sau dublati (daca t = 2) sirul care incepe la pozitia l, si se termina inaintea pozitiei r (sau pana la finalul sirului, daca r = lungimea sirului), indexand de la 0.
Restricţii
- T ≤ 1000
- lungimea oricarui sir in input ≤ 1000
- Pentru a rezolva corect problema, trebuie ca Q ≤ 1011.
- Pentru a rezolva corect problema, indicii dati in output trebuie sa se refera la intervale ce exista in sir la momentul operatiei.
- Se acepta oricare solutie corecta.
Exemplu
| misakatelefon.in | misakatelefon.out |
|---|---|
| 2 abcabc accc abc z | 8 2 0 6 2 0 12 2 0 24 0 24 48 0 18 23 0 12 17 0 4 11 0 0 3 -1 |
