Fişierul intrare/ieşire:zombies.in, zombies.outSursăLot Seniori Deva, 2019, baraj 1
AutorLucian BicsiAdăugată deStarGold2Emanuel Nrx StarGold2
Timp execuţie pe test6 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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

SubtaskPunctajConstrâ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.inzombies.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

Explicaţie pentru primul exemplu

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?