Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | mdluffxor.in, mdluffxor.out | Sursă | AGM 2019, runda finala,ziua 1 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Patrick Sava •xtreme77 |
| Timp execuţie pe test | 3.5 sec | Limită de memorie | 512000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mdluffxor
MDLuffXor este un spirit liber si vrea sa fie regele piratilor din spatiu. Din pacate, intai are de facut putina munca administrativa. MDLuffXor trebuie sa se ocupe de diverse siruri de cufere cu comori, care sunt gasite intr-o anumita ordine. Fiecare sir contine unul sau mai multe cufere, iar fiecare cufar contine o comoara, cu o valoare un numar natural ce nu depaseste 109. Acestea sunt construite de inamicul sau, maleficul Xoro, ca sa il incurce – insa, Xoro nu stie, in niciun moment, valorile comorilor din cufere. Fiecare sir de cufere este fie:
- Un singur cufar, a carui valoare ii este encunoscuta lui Xoro. Aceasta valoare este generata aleatoriu.
- Un sir creat de Xoro, ale carui valori sunt egale cu o concatenare a doua siruri de cufere anterioare.
- Un sir creat de Xoro, ale carui valori sunt egale cu prefixul unui sir de cufere anterior.
- Un sir creat de Xoro, ale carui valori sunt egale cu sufixul unui sir de cufere anterior.
Totusi, este garantat ca orice sir va avea cel mult 1018 cufere. In orice moment, maleficul Xoro il poate intreba pe MDLuffXor care este valoarea a celei de a K-a mai valoroasa comoara (de la cea mai valoroasa la cea mai putin valoroasa) intr-un sir anume. Xoro nu se foloseste de aceasta informatie cand va construi urmatoarele cerinte. Fiind date sirurile de cufere, gaseste raspunsurile intrebarilor lui Xoro.
Date de intrare
Fişierul de intrare mdluffxor.in va contine pe primul rand un numar natural Q. Inputul va fi codificat intr-un mod neobisuit. Pentru a-l decoda, intai initializeaza o variabila de tip int last, cu 0. Pe urmatoarele Q randuri vei gasi una din urmatoarele:
- 1 x, insemnand ca un sir ce contine un singur cufar, cu o valoare egala cu x, apare.
- 2 x y, insemnand ca un nou sir, egal cu concatenarea celor de al (X⊕last)-lea si de al (Y⊕last)-lea siruri apare.
- 3 x l, insemnand ca un nou sir, egal cu prefixul de lungime l⊕last al celui de al (X⊕last)-lea sir apare.
- 4 x l, insemnand ca un nou sir, egal cu sufixul de lungime l⊕last al celui de al (X⊕last)-lea sir apare.
- 5 x K, reprezentand o intrebare pusa de Xoro: "care este a K-a (NU K⊕last) cea mai valoroasa comoara din al (x⊕last)-lea sir?”. Intr-o astfel de intrebare, presupune ca ans e raspunsul. Dupa aceea, schimba last in (17*last+ans) mod 666.013".
Sirurile sunt indexate incepand de la 1, in ordinea in care apar. Se garanteaza ca in input se va face referire doar la siruri care exista deja. Se remarca faptul ca ⊕ reprezinta operatorul binar XOR.
Date de ieşire
În fişierul de ieşire mdluffxor.out ...
Restricţii
- ... ≤ ... ≤ ...
- K ≤ 400
- Q ≤ 200.000
Exemplu
| mdluffxor.in | mdluffxor.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
