== include(page="template/taskheader" task_id="zombies") ==

Poveste şi cerinţă...

_Notă: Se recomanda folosirea compilatorului GNU C++ pe 32 de biti._
 
Tocmai ţi-ai descărcat ultima versiune a binecunoscutului joc Plante şi Zombi. Jocul se joacă pe un teren finit 2D în care vor apărea mai mulţi zombi. Fiecare zombie are o poziţie de început $(S[~x~], S[~y~])$ în care apare, o viteză de $v$ unităţi/secundă şi un şir de exact 15 mutări pe care le va face. O mutare este codificată printr-un caracter din mulţimea ${U, R, D, L}$ ("up", "right", "down", "left").
 
Zombii vor executa mutările secvenţial, pornind de la prima mutare. Fiecare zombie se va mişca în direcţia indicată de mutarea curentă timp de exact o secundă, după care va trece la mutarea următoare. De exemplu, dacă un zombie are viteză $3$, începe de pe poziţia $(2, 4)$ şi prima mutare este $U$, acesta va executa mutările $(2, 4) -> (2, 5) -> (2, 6) -> (2, 7)$ într-o secundă, după care va trece la următoarea mutare. Pentru mai multe informaţii, vezi explicaţiile.
 
Dacă un zombie a epuizat şirul iniţial de mutări, va continua cu şirul de mutări de la început, astfel că ei vor cicla prin setul de mutări la infinit. În mişcarea lor, doi zombi pot ocupa aceeaşi poziţie în acelaşi timp, fără a interfera unul cu altul.
 
Scopul nostru este de a neutraliza zombii, plasând *plante-laser* ({_eng. Laser Beans_}). O plantă va fi plasată la poziţia $(l[~x~], l[~y~])$ şi va avea setată una din cele patru direcţii ${U, R, D, L}$. Plantele vor neutraliza tot ce se va afla în direcţia lor. De exemplu, o plantă la poziţia $(2, 5)$ direcţionată spre $U$ va neutraliza tot ce se va afla pe poziţiile $(2, 5), (2, 6), (2, 7), (2, 8), (2, 9), ...$. Se observă că un zombie va fi neutralizat chiar şi în momentul în care acesta va ajunge pe poziţia plantei.
 
Care este numărul minim de plante-laser care trebuie plasate pentru ca fiecare zombie să fie neutralizat la un moment dat pe parcursul jocului?

h2. Date de intrare

Fişierul de intrare $zombies.in$ ...

Pe prima linie se afla *N* reprezentând numărul de zombii.
Pe urmatoarele *N* linii se află câte 3 numere *Sx Sy v* si un sir de 15 caractere *S* reprezentând parametrii fiecărui zombie aţa cum sunt descrişi în enunţ, in ordine.
 
*Se garantează că şirul de mutări ale fiecărui zombie are lungime exact 15.*

h2. Date de ieşire

În fişierul de ieşire $zombies.out$ ...

Pe prima linie se va afişa *M* reprezentând numărul minim de plante cerut.
Pe următoarele *M* linii se vor afişa parametrii fiecărei plante: 2 numere *lx ly* reprezentând poziţia plantei şi un caracter reprezentând direcţia laserului plantei respective.

h2. Restricţii

Pentru ca soluţia returnată să fie validă, trebuie ca numărul de plante-laser returnate să fie minimul posibil şi ca plantele să neutralizeze toţi zombii. De asemenea, plantele trebuie plasate în poziţii distincte, iar coordonatele $l[~x~]$ şi $l[~y~]$ trebuie să fie numere întregi între $-10^9^$ şi $10^9^$ inclusiv.

* $... ≤ ... ≤ ...$

h2. Punctare

h2. Exemplu

table(example). |_. Subtask |_. Punctaj |_. Constrângeri |
| 1
| 17 puncte
| Numărul de zombi este între 1 şi 100
Pentru fiecare zombie:
• -300 ≤ s[~x~], s[~y~] ≤ 300
• 1 ≤ v ≤ 300
|
| 2
| 34 de puncte
| Numărul de zombi este între 1 şi 2.000
Pentru fiecare zombie:
• -10^5^ ≤ s[~x~], s[~y~] ≤ 10^5^
• 1 ≤ v ≤ 10^5^
|
| 3
| 21 de puncte
| Numărul de zombi este între 1 şi 20.000
Pentru fiecare zombie:
• -10^6^ ≤ s[~x~], s[~y~] ≤ 10^6^
• 1 ≤ v ≤ 10^6^
|
| 4
| 28 de puncte
| Numărul de zombi este între 1 şi 50.000
Pentru fiecare zombie:
• -10^6^ ≤ s[~x~], s[~y~] ≤ 10^6^
• 1 ≤ v ≤ 10^6^
|

table(example). |_. zombies.in |_. zombies.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h2. Exemple

h3. Explicaţie

table(example). |_. zombies.in |_. zombies.out |
| 3
0 0 3 URURURURURURURU
10 5 1 LLLLLDDDRRRRRRR
15 0 2 UUUUUUUUUUUUUUU
| 1
-2 1 R
|
| 2
10 10 1 UUUUUUUUUUUUUUU
-1 -1 1 DDDDDDDDDDDDDDD
| 2
-1 11 R
-1 12 D
|

...

h3. Explicaţie pentru primul exemplu
!problema/zombies?Poza_Exemplu_1.png!

== include(page="template/taskfooter" task_id="zombies") ==
 

== include(page="template/taskfooter" task_id="zombies") ==