== include(page="template/taskheader" task_id="pelican") ==
Poveste și cerință...
Într-o minunată zi de primăvară, $*P*$ rățuște au ieșit la plimbare pe lac. Un pelican milităros, care stătea pe mal, a decis să facă instrucție cu nevinovatele rațe. Pentru aceasta, a cartografiat imediat lacul și l-a reprezentat ca o matrice cu $*N*$ linii (numerotate de la $*0*$ la $*N − 1*$ de sus în jos) și $*N*$ coloane (numerotate de la $*0*$ la $*N − 1*$ de la stânga la dreapta). Astfel, poziția oricărei rațe pe lac poate fi identificată prin linia și coloana pe care se află rața. Rațele sunt orientate cu fața spre una dintre direcțiile $*Nord*$, $*Sud*$, $*Est*$, $*Vest*$. Pelicanul a codificat direcțiile [$1$], [$2$], [$3$], $4$ ca în figură.
!problema/pelican?rata.png!
Când pelicanul strigă: ,,Comanda la mine!” rațele trebuie să execute simultan cele *K* comenzi pe care le dă pelicanul. Comenzile pelicanului sunt codificate astfel:
table(example).
|_. Comanda |_. Efect |_. Exemplu |
| $A _nr_$
| Rața avansează cu _nr_ poziții în direcția
spre care este orientată. Dacă avansând
depășește marginea tablei de joc va intra
pe latura opusă.
| De exemplu, pe un lac 5 × 5, o rață plasată
în poziția (1, 3) cu orientare 1 ([*Nord*]), executând
comanda *A* 3 se va deplasa astfel:
(1, 3) → (0, 3) → (4, 3) → (3, 3).
|
| $R _nr_$
| Rața se rotește cu _nr_ · 90° în sens orar,
unde _nr_ ∈ { 1, 2, 3, 4 }.
| De exemplu, dacă orientarea inițială a raței este
1 ([*Nord*]), comanda *R* 2 va schimba orientarea spre 3 ([*Sud*]).
|
| $Z _nr_$
| Rața zboară pe linia [_nr_] / [*N*] și coloana
[_nr_] % [*N*], păstrând orientarea. Se garantează
că [_nr_] / [*N*] ∈ { 0, 1, . . . , [*N*]−1 }.
| De exemplu, pe un lac 5 × 5, după executarea
comenzii *Z* 7, rața va ajunge pe linia 1 și coloana 2.
|
h2. Cerințe
Scrieți un program care, cunoscând poziția inițială pe lac a celor $*P*$ rațe și succesiunea comenzilor pelicanului, determină poziția finală a fiecărei rațe.
h2. Date de intrare
Fișierul de intrare $pelican.in$ ...
Fișierul de intrare $pelican.in$ conține pe prima linie trei numere naturale [$*N* *P* [*K*]$], cu semnificația din enunț. Pe următoarele $*P*$ linii sunt date câte $3$ numere naturale $*i* *j* [*d*]$ $(0 ≤ *i*, *j* < *N* și 1 ≤ *d* ≤ 4)$ cu semnificația că pe linia $*i*$ și coloana $*j*$ se găsește o rață orientată în direcția [$*d*$]. Ultimele $*K*$ linii conțin cele $*K*$ comenzi, câte o comandă pe o linie, în formatul specificat în enunț (un caracter din mulțimea $′A′$ , $′R′$, $′Z′$ și un număr natural). Valorile scrise pe aceeași linie sunt separate de câte un spațiu.
h2. Date de ieșire
În fișierul de ieșire $pelican.out$ ...
Fișierul de ieșire $pelican.out$ va conține $*P*$ linii. Pe linia $i$ va fi scrisă poziția celei de a [$i$]-a rațe din fișierul de intrare (linia și coloana separate printr-un singur spațiu) după executarea ı̂n ordine a celor $*K*$ comenzi.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ *N* ≤ 1000$
* $1 ≤ *P* ≤ 10 000$
* $1 ≤ *K* ≤ 100 000$
* Mai multe rațe pot ocupa aceeași poziție.
* Se garantează că datele din fișierul de intrare sunt corecte.
table(example).
|_. # |_. Punctaj |_. Restricții |
| 1 | 76 | Pentru teste valorând $76$ de puncte fișierul de intrare nu conține comanda $*Z*$. |
| 2 | 20 | Pentru teste valorând $20$ de puncte *N* ≤ 100, *P* ≤ 100 și *K* ≤ 1000. |
| 3 | 36 | Pentru teste valorând $36$ de puncte *N* > 100, 1000 ≤ *P* ≤ 5000 și *K* ≤ 50000. |
h2. Exemplu
table(example).
table(example).
|_. pelican.in |_. pelican.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 3 4
1 1 2
2 3 1
3 1 4
A 3
R 3
A 1
A 3
| 2 4
4 4
2 3
|
h3. Explicație
...
Lacul are 5 linii și 5 coloane. Pe lac există 3 rațe poziționate ca ı̂n figură.
!problema/pelican?expicatie1.png!
Pelicanul dă 4 comenzi pe care toate cele 3 rațe le execută ı̂n ordine.
Rațele execută comanda A 3
!problema/pelican?explicatie2.png!
Rațele execută comanda R 3 (se rotesc cu 270 ◦ ı̂n sens orar)
!problema/pelican?explicatie3.png!
Rațele execută comanda A 1
!problema/pelican?explicatie4.png!
Rațele execută comanda A 3
!problema/pelican?explicatie5.png!
== include(page="template/taskfooter" task_id="pelican") ==
