==Include(page="template/taskheader" task_id="zc")==
==Include(page="template/raw")==
Zota & Chidil
Zota si Chidil s-au certat. De aceasta data, Zota, dorind sa se razbune, planuieste sa insire o serie de capcane in padurea prin care Chidil obisnuieste sa se plimbe. Astfel, folosind o formula magica, el asterne o capcana in mai multe celule ale padurii. Toate celulele care se afla la o distanta Manhattan mai mica sau egala cu 2 de capcana sunt si ele afectatate.
In imaginea de mai jos capcana este reprezentata prin "O" iar celelalte celule afectate sunt marcate cu "X".
.......
...X...
..XXX..
.XXOXX.
..XXX..
...X...
.......
Chidil isi planifica intotdeauna traseul. El porneste intotdeauna din celula cu coordonate (0, 0). Drumul lui este descris printr-o pereche (D, x) unde D apartine multimii {N, E, S, V}, iar x este un numar natural nenul. Aceasta inseamna ca din pozitia in care se afla, va face x pasi in directia D.
Desi afla de planul malefic al lui Zota, Chidil nu vrea sa isi schimbe traseul cu nici un chip. Prefera sa afle cate celule din traseul lui contin capcane sau sunt afectate de capcane, pentru a sti exact cat praf magic pentru neutralizarea celulelor sa ia la el.
h2. Cerinta
Ajutati-l pe Chidil sa afle raspunsul !
h2. Date de Intrare
Linia 1 a fisierului de intrare se afla doua numere naturale N si M, reprezentand numarul de capcane intinse de Zota, respectiv numarul de perechi (D, x)conform carora Chidil urmeaza sa se deplaseze.
Liniile 2 .. N + 1 contin cate o pereche de numere x, y, ce reprezinta coordonatele capcanelor.
Liniile N + 2 .. N + M + 1 contin cate o pereche de forma D, x, cu semnificatia ca Chidil face x pasi in directia D.
h2. Date de Iesire
Fisierul de iesire va contine pe prima linie numarul de celule periculoase care trebuie neutralizate de Chidil in drumul sau.
h2. Restrictii si precizari
* 1 <= N, M <= 100 000
* Coordonatele lui Chidil nu vor iesi niciodata din intervalul [- 2 000 000 000, 2 000 000 000]
* chiar daca celula de pornire a lui Chidil contine sau este afectata de o capcana, nu este nevoie de praf magic pentru a o neutraliza
* desi o celula poate fi afectata de mai multe capcane, este nevoie de o singura unitate de praf magic pentru a o neutraliza
* efectul prafului magic este temporar; de fiecare data cand Chidil trece printr-o celula afectata, are nevoie de praf magic pt a o neutraliza
h2. Exemplu
==Include(page="template/taskheader" task_id="zc")==
Zota si Chidil s-au certat. De aceasta data, Zota, dorind sa se razbune, planuieste sa insire o serie de capcane in padurea prin care Chidil obisnuieste sa se plimbe. Astfel, folosind o formula magica, el asterne o capcana in mai multe celule ale padurii. Toate celulele care se afla la o distanta Manhattan mai mica sau egala cu _2_ de capcana sunt si ele afectatate.
In imaginea de mai jos capcana este reprezentata prin $O$ iar celelalte celule afectate sunt marcate cu $X$.
$.......$
$...X...$
$..XXX..$
$.XXOXX.$
$..XXX..$
$...X...$
$.......$
Chidil isi planifica intotdeauna traseul. El porneste intotdeauna din celula cu coordonate (0, 0). Drumul lui este descris printr-o pereche ({$D$}, {$x$}) unde D apartine multimii {$N$, $E$, $S$, $V$}, iar $x$ este un numar natural nenul. Aceasta inseamna ca din pozitia in care se afla, va face $x$ pasi in directia $D$.
Desi afla de planul malefic al lui Zota, Chidil nu vrea sa isi schimbe traseul cu nici un chip. Prefera sa afle cate celule din traseul lui contin capcane sau sunt afectate de capcane, pentru a sti exact cat praf magic pentru neutralizarea celulelor sa ia la el.
h2. Cerinta
Ajutati-l pe Chidil sa afle raspunsul!
h2. Date de intrare
Pe prima linie a fisierului de intrare $zc.in$ se afla doua numere naturale $N$ si $M$, reprezentand numarul de capcane intinse de Zota, respectiv numarul de perechi ({$D$}, $x$) conform carora Chidil urmeaza sa se deplaseze.
Liniile $2 .. N+1$ contin cate o pereche de numere ({$x$} {$y$}), ce reprezinta coordonatele capcanelor.
Liniile $N+2 .. N+M+1$ contin cate o pereche de forma $D$, $x$, cu semnificatia ca Chidil face $x$ pasi in directia $D$.
h2. Date de iesire
Fisierul de iesire $zc.out$ va contine pe prima linie numarul de celule periculoase care trebuie neutralizate de Chidil in drumul sau.
h2. Restrictii si precizari
* $1 ≤ N, M ≤ 100 000$
* Coordonatele lui Chidil nu vor iesi niciodata din intervalul [$-2 000 000 000$, $2 000 000 000$]
* Chiar daca celula de pornire a lui Chidil contine sau este afectata de o capcana, nu este nevoie de praf magic pentru a o neutraliza
* Desi o celula poate fi afectata de mai multe capcane, este nevoie de o singura unitate de praf magic pentru a o neutraliza
* Efectul prafului magic este temporar; de fiecare data cand Chidil trece printr-o celula afectata, are nevoie de praf magic pt a o neutraliza
h2. Exemplu
table(example). |_. zc.in |_. zc.out |
| 2 8
5 6
12 10
N 3
E 6
N 7
E 2
S 3
E 6
N 6
V 3
| 4 |
h3. Explicatii
$...........####............$
$............X.#............$
$...........XXX#............$
$......###.XXOX{%{color:red}#%}............$
$......#.#..XXX#............$
$.....X#.#...X.#............$
$....XX{%{color:red}#%}.#######............$
$...XXO{%{color:red}#%}X...................$
$....XX{%{color:red}#%}....................$
$.....X#....................$
$#######....................$
$#..........................$
$#..........................$
$#..........................$
==Include(page="template/taskfooter" task_id="zc")==
| zc.in | zc.out | Explicatii |
| 2 8 | 4 | ...........####............ |
| 5 6 | | ............X.#............ |
| 12 10 | | ...........XXX#............ |
| N 3 | | ......###.XXOX#............ |
| E 6 | | ......#.#..XXX#............ |
| N 7 | | .....X#.#...X.#............ |
| E 2 | | ....XX#.#######............. |
| S 3 | | ...XXO#X................... |
| E 6 | | ....XX#.................... |
| N 6 | | .....X#.................... |
| V 3 | | #######.................... |
| | | #.......................... |
| | | #.......................... |
| | | #.......................... |
==Include(page="template/taskfooter" task_id="zc")==
