| Fişierul intrare/ieşire: | zombies.in, zombies.out | Sursă | Lot Seniori Deva, 2019, baraj 1 |
| Autor | Lucian Bicsi | Adăugată de |  Emanuel Nrx •StarGold2 |
| Timp execuţie pe test | 3 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zombies
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 (Sx, Sy) î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 (lx, ly) ş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?
Date de intrare
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.
Date de ieşire
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.
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 lx şi ly trebuie să fie numere întregi între -109 şi 109 inclusiv.
Punctare
| Subtask | Punctaj | Constrângeri |
|---|---|---|
| 1 | 17 puncte | Numărul de zombi este între 1 şi 100 Pentru fiecare zombie: • -300 ≤ sx, sy ≤ 300 • 1 ≤ v ≤ 300 |
| 2 | 34 de puncte | Numărul de zombi este între 1 şi 2.000 Pentru fiecare zombie: • -105 ≤ sx, sy ≤ 105 • 1 ≤ v ≤ 105 |
| 3 | 21 de puncte | Numărul de zombi este între 1 şi 20.000 Pentru fiecare zombie: • -106 ≤ sx, sy ≤ 106 • 1 ≤ v ≤ 106 |
| 4 | 28 de puncte | Numărul de zombi este între 1 şi 50.000 Pentru fiecare zombie: • -106 ≤ sx, sy ≤ 106 • 1 ≤ v ≤ 106 |
Exemple
| 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 |
