Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | walls.in, walls.out | Sursă | RMMS 2011 - Ziua 1 |
| Autor | Andrei Homescu, Catalin-Stefan Tiseanu | Adăugată de |  Andrei Parvu •andrei.12 |
| Timp execuţie pe test | 0.275 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Walls
Se dau N ziduri dreptunghiulare în plan, aşezate unul după altul de la stânga la dreapta, toate având baza comună iar 2 ziduri consecutive între ele un spaţiu gol de 1 celulă (aşezarea este exact ca în jocul Ziduri). Fiecare zid i are înălţimea Hi şi lăţimea Wi şi este alcătuit din W*H celule pătrate de dimensiune 1×1. Colţul din stânga-jos al primului zid este celula de coordonate (1,1).
Inamicul doreşte să distrugă cât mai multe ziduri, folosind un tun care trage cu ghiulele. Acest tun are o poziţie reglabilă, putând trage cu o ghiulea din orice punct în care nu se află o celulă a unui zid. Tunul trage cu o ghiulea care se deplaseaza orizontal dinspre dreapta spre stânga până loveşte celula unui zid, pe care o distruge. Ghiuleaua este distrusă la rândul ei în această coliziune.
Dacă tunul distruge toate celulele de pe un nivel al unui zid, atunci acel nivel şi toate cele de deasupra sa sunt distruse si dispar. Din zid vor rămâne doar celulele aflate sub nivelul distrus.
Ştiind că inamicul trage cu tunul de M ori, să se calculeze pentru fiecare tragere ce celulă loveşte (dacă loveşte vreuna) şi dacă distrugerea celulei cauzează căderea nivelurilor superioare ale zidului.
Date de intrare
Fişierul de intrare walls.in va conţine pe prima linie numărul N, apoi N linii cu perechile Hi şi Wi. Urmează numărul M, apoi M linii cu coordonatele tunului la fiecare tragere.
Date de ieşire
Fişierul de ieşire walls.out va conţine câte o linie pentru fiecare ghiulea. Dacă ghiuleaua nu a lovit nimic, linia conţine doar şirul MISS. Dacă ghiuleaua a lovit o celulă, linia are forma:
HIT x_celula zid cazut
unde:
x_celula = coordonata celulei lovite
zid = zidul lovit de ghiulea
cazut = YES dacă a căzut partea superioara a zidului sau NO daca nu; se afişează YES aici şi dacă celula distrusă este pe nivelul cel mai înalt al zidului
Restricţii
- 1 ≤ N, M ≤ 100.000
- 1 ≤ W, H ≤ 2.000.000.000
Exemplu
| walls.in | walls.out |
|---|---|
| 4 2 4 2 6 2 4 2 2 7 10 3 11 3 3 4 3 4 12 9 13 4 14 4 | HIT 8 3 NO HIT 7 3 YES HIT 2 1 NO HIT 1 1 YES MISS HIT 5 2 NO HIT 4 2 YES |
Explicaţie
Este lovit zidul 3 in celula (8,3)
Este lovit zidul 3 in (7,3), cad nivelurile 3 si 4
Este lovit zidul 1 in celula (2,4)
Este lovit zidul 1 in (1,4), cade nivelul 4
Nu exista nici un zid de inaltime 9
Este lovit zidul 2 in celula (5,3)
Este lovit zidul 2 in (4,3), cad nivelurile 3, 4, 5, 6
