Vedúci sedia v T21, nič nerobia a zrazu si spomenú, že možno by chcelo aj zverejniť nové úlohy do KSP.
„Nejak sme zabudli na prvú úlohu, mali by sme s tým niečo spraviť“, povedal Stanko.
„No dobre, tak ja rýchlo spravím vstupy a vy si napíšte zadanie, to sa mi robiť nechce“, hovorí Andrej.
„Joooj ja by som to zadanie možno spravil, ale nemám pri sebe počítač, budem vám to zadanie diktovať a niekto ho prosím píšte“, sťažuje sa Miško.
Miestnosť, v ktorej sú vedúci, má tvar obdĺžnika s $n$ riadkami a $m$ stĺpcami, teda dokopy $n \cdot m$ políčok. Počítač, na ktorom sa dá písať zadanie prvej úlohy do KSP, sa nachádza v riadku $a$ a stĺpci $b$. Ako ste mohli vidieť, tak vedúcim sa zadanie písať nechce, takže chcú byť od počítača čo najďalej. Kam sa majú vedúci postaviť?
Vzdialenosť medzi 2 políčkami počítame ako minimálny počet políčok, cez ktoré máme prejsť, aby sme sa dostali z jedného na druhé s tým, že sa vieme posúvať iba na hranou susediace políčka (Manhattanská vzdialenosť).
V prvom riadku vstupu sú rozmery miestnosti, teda čísla $n$ a $m$ ($1 \leq n,m \leq 10^6$) oddelené medzerou.
V druhom riadku vstupu je pozícia počítača, teda 2 čísla $a$ ($1 \leq a \leq n$) a $b$ ($1 \leq b \leq m$).
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $1 \leq n \leq$ | $1$ | $10^6$ | $10^6$ | $10^6$ |
| $1 \leq m \leq$ | $10^6$ | $10^6$ | $10^6$ | $10^6$ |
| $1 \leq n \cdot m \leq$ | $10^6$ | $10^6$ | $10^{12}$ | $10^{12}$ |
Navyše je garantované, že v 3. sade je miestnosť tvaru štvorca, teda $n = m$.
Vypíš jeden riadok a v ňom pozíciu vedúcich, teda 2 čísla oddelené medzerou - riadok a stĺpec.
Je garantované, že vždy je takáto pozícia práve 1, riešenie je teda vždy jednoznačné.
1 2
1 1
1 2
Vieme byť buď hneď pri počítači, čo nechceme, alebo pôjdeme na druhé políčko a budeme vzdialený 1 od počítača
.X
3 4
1 2
3 4
Najviac sa nám oplatí byť v pravom dolnom rohu - budeme potom vzdialený 4 políčka od počítača
.X..
....
....
Epická miestnosť na matfyze, kde sídli KSP ↩
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete