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

Poveste şi cerinţă...

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").

h2. Date de intrare

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.

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

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.

h2. Date de ieşire

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.

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

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. Restricţii

h2. Detalii de implementare

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

Veţi implementa funcţia cu următorul antet:

h2. Exemplu

== code(cpp) |
 
std::vector<Plant> minimum_plants(std::vector<Zombie> zombies)
 
==
 
Structurile de date folosite în cadrul interacţiunii sunt descrise în fişierul *zombies.h* şi au următoarea descriere:
 
== code(cpp) |
 
struct Zombie {int sx, sy, v; string moves; };
struct Plant {int lx, ly; char dir; };
 
==
 
Funcţia $minimum_plants$ va fi apelată o singură dată, parametrii având specificaţiile din enunţ. *Se garantează că şirul de mutări ale fiecărui zombie are lungime exact 15.*
 
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
 
table(example). |_. Subtask |_. Punctaj |_. Constrângeri |
| 1
| 17 puncte
| Numărul de zombi este între 1 şi 100
Pentru fiecare zombie:
• -300 &le; s[~x~], s[~y~] &le; 300
• 1 &le; v &le; 300
|
| 2
| 34 de puncte
| Numărul de zombi este între 1 şi 2.000
Pentru fiecare zombie:
• -10^5^ &le; s[~x~], s[~y~] &le; 10^5^
• 1 &le; v &le; 10^5^
|
| 3
| 21 de puncte
| Numărul de zombi este între 1 şi 20.000
Pentru fiecare zombie:
• -10^6^ &le; s[~x~], s[~y~] &le; 10^6^
• 1 &le; v &le; 10^6^
|
| 4
| 28 de puncte
| Numărul de zombi este între 1 şi 50.000
Pentru fiecare zombie:
• -10^6^ &le; s[~x~], s[~y~] &le; 10^6^
• 1 &le; v &le; 10^6^
|
 
h2. Exemple

table(example). |_. zombies.in |_. zombies.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 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

...

TODO: pune poza

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