Fişierul intrare/ieşire:misakatelefon.in, misakatelefon.outSursăAGM 2019, runda finala
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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:

  1. Sa selecteze un substring pe care sa il stearga (abcd devine ad).
  2. 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.inmisakatelefon.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?