Fişierul intrare/ieşire:sir8.in, sir8.outSursăLot Sovata 2014 Seniori Baraj 1
AutorAlexandru CazacuAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test1 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sir8

S, fost olimpic la informatică, încearcă să prevină atacurile de securitate ce pot apărea în reţeaua lui. Astfel, el are un şir de caractere special, preferat de el ca şi parolă. Pentru a verifica dacă parola lui este suficient de puternică, acesta a creat o listă L de dimensiune K cu parolele preferate de hackeri. Preventiv din fire, acesta doreşte să facă asupra parolei următoarele operaţii:
- Insert, se insereaza o literă C la o poziţie X. În acest caz, toate caracterele care au o poziţie mai mare sau egală cu X se vor muta cu o poziţie la dreapta, iar pe poziţia X va fi inserat caracterul C.
- Query, se întreabă dacă al Y-lea cuvânt din lista de parole coincide cu subsecvenţa de aceeaşi lungime care se termina pe pozitia Z în şirul special. Ultimul caracter al celui de-al Y-lea cuvânt va trebui să coincidă cu caracterul de pe poziţia Z, penultimul caracter al celui de-al Y-lea cuvânt va trebui să coincidă cu caracterul de pe poziţia Z-1 ş.a. 

Cerinta

Cunoscându-se şirul de caractere special, K – lungimea listei de cuvinte, cele K cuvinte şi o succesiune de Q operaţii, să se răspundă la operaţiile de tip Query.

Date de intrare

Pe prima linie a fişierului sir8.in se află şirul special. Pe cea de-a doua linie se află K, lungimea listei de cuvinte. Pe următoarele K linii se află parolele ce aparţin listei, câte una pe linie. Pe următoarea linie, se află Q, numărul de operaţii. Următoarele Q linii descriu aceste operaţii. O linie descrie o operaţie astfel:
- 0 poz c a b Primul număr, zero, reprezintă tipul operaţiei, respectiv insert. C reprezintă caracterul care va fi inserat. Folosind poz, a şi b, vom calcula poziţia pe care caracterul va fi inserat. Dacă rezultatul ultimei operaţii de tip Query a fost 0, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: poz ^ a (unde operatorul ^ reprezinta sau exclusiv – xor ). Dacă rezultatul ultimei peraţii de tip Query a fost 1, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: poz ^ b. În caz că operaţia curentă nu a fost precedată de nicio operaţie de tip Query, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: poz ^ a.
- 1 poz ind a b Primul număr, unu, reprezintă tipul operaţiei, respectiv query. Al treilea număr, ind, reprezintă indicele cuvântului din lista pe care vom efectua operaţia de tip query. Folosind poz, a şi b, vom calcula poziţia pe care se termină al ind-lea cuvânt din lista de parole. Dacă rezultatul ultimei operaţii de tip Query a fost 0, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: poz ^ a (unde operatorul ^ reprezintă sau exclusiv – xor). Dacă rezultatul ultimei operaţii de tip Query a fost 1, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: poz ^ b. În caz că operaţia curentă nu a fost precedată de nicio operaţie de tip Query, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: poz ^ a.

Date de ieşire

Pentru fiecare operaţie de tip query, se va afişa 0 în cazul în care cuvântul nu se potriveşte, respectiv 1 în caz că se potriveşte.

Restricţii

  • Se garantează că suma lungimilor cuvintelor din dicţionar este mai mică decât 800 000
  • Se garantează că lungimea maximă a şirului special nu depăşeşte 60 000 după ce s-au efectuat toate operaţiile Insert.
  • Numărul de operaţii este mai mic sau egal cu 85 000

Exemplu

sir8.insir8.out
photoshop
2
hoto
goto
4
1 14643 1 14646 27787
0 88412 g 38665 88415
1 41453 2 37823 41451
1 78120 1 98233 78125
1
1
0

Explicaţie

În urma operaţiei xor, fişierul se transformă în:

photoshop
2
hoto
goto
4
1 5 1
0 3 g
1 6 2
1 5 1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?