Fişierul intrare/ieşire:walls.in, walls.outSursăRMMS 2011 - Ziua 1
AutorAndrei Homescu, Catalin-Stefan TiseanuAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.55 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

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 Wi şi Hi. 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.inwalls.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,4)
Este lovit zidul 2 in (4,4), cad nivelurile 4, 5, 6

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content