Fişierul intrare/ieşire:sir3.in, sir3.outSursăLot Sovata 2014
AutorAlexandru CazacuAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test3 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Sir3 (lot liceu)

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.

Cerinţă

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 sir3.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 XOR a (unde operatorul XOR reprezinta sau exclusiv). 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 XOR 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 XOR 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 XOR a (unde operatorul XOR reprezintă sau exclusiv). 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 XOR 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 XOR a.

Date de ieşire

În fişierul de ieşire sir3.out, pe câte o linie, 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

sir3.insir3.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