== include(page="template/taskheader" task_id="sir8") ==
Poveste şi cerinţă...
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.
h2. 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.
h2. Date de intrare
Fişierul de intrare $sir8.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $sir8.out$ ...
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.
h2. 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$
h2. Exemplu
table(example). |_. sir8.in |_. sir8.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. 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$
== include(page="template/taskfooter" task_id="sir8") ==
