== include(page="template/taskheader" task_id="walls") ==
Poveste şi cerinţă...
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 $H{~i~}$ şi lăţimea $W{~i~}$ şi este alcătuit din $W*H$ celule pătrate de dimensiune $1x1$. 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.
h2. Date de intrare
Fişierul de intrare $walls.in$ ...
Fişierul de intrare $walls.in$ va conţine pe prima linie numărul $N$, apoi $N$ linii cu perechile $W{~i~}$ şi $H{~i~}$. Urmează numărul $M$, apoi $M$ linii cu coordonatele tunului la fiecare tragere.
h2. Date de ieşire
În fişierul de ieşire $walls.out$ ...
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
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 100.000$
* $1 ≤ W, H ≤ 2.000.000.000$
h2. Exemplu
table(example). |_. walls.in |_. walls.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. 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
== include(page="template/taskfooter" task_id="walls") ==
