Iskanje zaklada

# Iskanje zaklada Peter in Robi, njegov robotski prijatelj, se igrata igro Iskanje zaklada. Peter si zamisli, da je pod neko "celico" v njegovi sobi skrit zaklad, Robi pa jo mora poiskati. Peter Robiju vsakokrat dá enega od devetih ukazov: SZ, S, SV, V, JV, J, JZ, Z ali NE_GREM_SE_VEC. Ukaz SZ pove, da se iskani zaklad nahaja severozahodno od Robijevega trenutnega položaja (torej ne čisto severno in ne čisto zahodno, ampak nekje vmes --- to lahko pomeni tudi "skoraj" severno ali "skoraj" zahodno). Ukaz S pove, da se iskani zaklad nahaja točno severno od Robijevega položaja. Ostali eno- ali dvočrkovni ukazi se nanašajo na ostale smeri neba (SV = severovzhodno, V = vzhodno, JV = jugovzhodno, J = južno, JZ = jugozahodno, Z = zahodno), ukaz NE_GREM_SE_VEC pa pove, da se je Peter igre naveličal. Takrat mu mora Robi razkriti koordinate najmanjšega pravokotnika, na katerem se na podlagi Petrovih ukazov zanesljivo nahaja zaklad. Robi igra optimalno. Najprej se postavi na sredino sobe, po vsakem Petrovem ukazu (razen seveda po ukazu NE_GREM_SE_VEC) pa se postavi na sredino pravokotnega območja, ki lahko po doslej zbranih podatkih vsebuje zaklad. Sredina območja, v katerem ima skrajna severozahodna (tj. zgornja leva) celica koordinati $(x_1, y_1)$, skrajna jugovzhodna (tj. spodnja desna) pa koordinati $(x_2, y_2)$, je celica s koordinatama $(\lfloor(x_1 + x_2) / 2\rfloor$, $\lfloor(y_1 + y_2) / 2\rfloor)$, pri čemer $\lfloor.\rfloor$ pomeni zaokrožitev navzdol. Peter je muhast in lahko Robiju daje tudi protislovne ukaze. Če Robi zazna protislovje, mu mora to jasno sporočiti. ## Vhod V prvi vrstici se nahajata števili $D_x$ in $D_y$, ki podajata dolžino sobe v koordinatah $x$ in $y$. (Skrajna severozahodna celica ima koordinati $(0, 0)$, skrajna jugovzhodna pa $(D_x - 1, D_y - 1)$.) Nato sledi poljubno mnogo vrstic, od katerih vsaka vsebuje niz SZ, S, SV, V, JV, J, JZ ali Z. Vhod se zaključi z vrstico, ki vsebuje niz NE_GREM_SE_VEC. ## Izhod Izpiši koordinate najmanjšega pravokotnika, ki glede na Petrove ukaze zanesljivo vsebuje zaklad. Koordinate izpiši v obliki $x_1\ \ y_1\ \ x_2\ \ y_2$ pri čemer sta $x_1$ in $y_1$ koordinati skrajne severozahodne, $x_2$ in $y_2$ pa koordinati skrajne jugovzhodne celice pravokotnika. Med zaporednima koordinatama stoji natanko en presledek. Če so Petrovi ukazi protislovni, izpiši niz PROTISLOVJE. ## Primer 1 ### Vhod ``` 15 10 SV J NE_GREM_SE_VEC ``` ### Izhod ``` 11 2 11 3 ``` ### Komentar Robi na začetku ve samo to, da se zaklad nahaja v pravokotniku $((x_1, y_1), (x_2, y_2)) = ((0, 0), (14, 9))$. Postavi se na sredinsko celico, torej na koordinati $(x, y) = (7, 4)$. Peter mu odgovori s SV, zato Robi sedaj ve, da se zaklad nahaja v pravokotniku $((8, 0), (14, 3))$. Ko se postavi na celico $(11, 1)$, dobi odgovor J. Zdaj ve, da je zaklad v pravokotniku $((11, 2), (11, 3))$. Ta pravokotnik je tudi rezultat tega primera, saj se Peter naveliča igre. ## Primer 2 ### Vhod ``` 15 10 SV J JZ NE_GREM_SE_VEC ``` #### Izhod ``` PROTISLOVJE ``` ### Komentar Robi po odgovorih SV in J ugotovi, da se zaklad nahaja v pravokotniku $((11, 2), (11, 3))$. Postavi se na celico $(11, 2)$, Peter pa mu odgovori z JZ. Ker po doslej zbranih podatkih jugozahodno od celice $(11, 2)$ ne more biti zaklada (lahko je kvečjemu južno), se je Peter očitno nekje zmotil ali zlagal. ## Omejitve * $D_x, D_y \in [1, 10^9]$. ## Podnaloge 1. podnaloga (30 točk): možni so samo ukazi V, Z in NE_GREM_SE_VEC. 2. podnaloga (30 točk): možni so samo ukazi S, J, V, Z in NE_GREM_SE_VEC. 3. podnaloga (40 točk): možni so vsi ukazi.