Zadanie

Každý vie, aký je Denis farmár. Na svojom pozemku chová veľa rôznych zvieratiek, ako napríklad psíka Toma, zopár kôz a stádo kráv. Psík Tom má náročnú úlohu – stráži kravy, aby sa netúlali mimo Denisov pozemok (sám Denis ich nestráži, radšej pozerá futbal na svojom iPade). Tom nie je zrovna inteligentný pes. Napriek tomu je schopný postrážiť všetky zvieratká okrem kravy Rysule. Tá je veľmi múdra, a často sa jej podarí Toma prechytračiť a opustiť pozemok. Všimla si totiž, že ak sa pohybuje iba vertikálne alebo horizontálne, tak ju Tom nezbadá. Potom chudák Denis musí Rysuľu hľadať a často pritom zmešká druhý polčas. Keďže sa blíži Liga majstrov, Denis si nemôže dovoliť zmeškať zápas kvôli Rysuli. Musí preto oplotiť svoj pozemok.

Denis sa rozhodol, že zabije dve muchy jednou ranou. Vyženie všetky zvieratá na pastviny, a kým sa budú pásť, on bude stavať plot. Zabudol ale, že Rysuľa mu bude chcieť ujsť, a on už nechce dopustiť aby mu zase zdrhla.

Denis sa naučil techniku Assembler, to znamená, že jeho runtime (beh) je nekonečne rýchly. Plot ale stavia pomaly, konkrétne tak rýchlo, ako sa Rysuľa pohybuje.

Úloha

Denisov pozemok je obdĺžnik \(r \times s\) políčok. Na jednom z týchto políčok sa na začiatku pasie krava Rysuľa, ktorá mu chce z neho ujsť. Každú sekundu sa stanú nasledovné dve veci (v takomto poradí):

  • Denis postaví kus plota o dĺžke strany jedného políčka. Tento kus oddelí niektoré okrajové políčko jeho pozemku od vonkajšieho sveta (v prípade rohového políčka ho oddelí iba z jednej strany). Keďže Denis behá nekonečne rýchlo, môže túto časť plota postaviť kdekoľvek, nezávisle na tom, kde bol v predošlej sekunde.

  • Rysuľa sa pohne o jedno políčko v jednom zo štyroch základných smerov. Ak je Rysuľa na kraji pozemku a nebráni jej plot, môže z neho takýmto spôsobom ujsť.

Denis vyhrá, ak sa mu podarí oplotiť celý pozemok (teda postaviť všetkých \(2 (r+s)\) častí plotu) bez toho, aby z neho Rysuľa ušla. Rysuľa vyhrá, ak sa jej podarí ujsť z pozemku skôr, než ho Denis celý oplotí.

Táto úloha je interaktívna!

V tejto úlohe si váš program zahrá proti nášmu programu. Váš program bude hrať za Denisa, náš za Rysuľu.

Váš program bude striedavo vypisovať ťahy, ktoré chce urobiť a načítavať ťahy, ktoré urobí ten náš, až kým niektorý program nevyhrá.

Formát vstupu

Na začiatku hry dostanete na vstupe rozmery mapy a začiatočnú pozíciu kravy. V prvom riadku budú dve medzerou oddelené celé čísla \(r\) a \(s\) (\(1 \leq r,s \leq 20\,000\)) – rozmery Denisovho pozemku. V ďalšom riadku sú čísla \(x\) a \(y\) – počiatočná pozícia kravy Rysule.

Následne môžete urobiť svoj prvý ťah a vypísať ho na výstup. Po každom ťahu, ktorý urobíte (a vypíšete), dostanete na vstupe náš ďalší ťah. Ten bude mať formu dvojice čísel \(x\) a \(y\) – pozícia, kam sa Rysuľa pohla. Platí \(1 \leq x \leq s\) a \(1 \leq y \leq r\). Ak sa Rysuli podarí ujsť, váš program sa to už nedozvie (aj tak by s tým už nemal čo robiť).

Rozmery mapy a počiatočná pozícia kravy budú vždy také, že existuje víťazná stratégia pre Denisa. To znamená, že váš program by mal byť schopný vyhrať bez ohľadu na to, ako dobre bude hrať ten náš.

V jednotlivých sadách testovacích vstupov navyše platí:

číslo sady obmezenie na \(r\), \(s\) Rysuľa
1 \(1 \leq r, s \leq 100\) Rysuľa sa nepokúsi ujsť z pozemku (na získanie
bodov ho stačí korektne oplotiť).
2 \(1 \leq r, s \leq 1000\) Rysuľa najviac raz príde na okraj pozemku. Ak vtedy
narazí na plot, vzdá to a už sa nepokúsi utiecť.
3 \(1 \leq r, s \leq 1000\) Rysuľa sa zo všetkých síl snaží ujsť.
4 \(1 \leq r, s \leq 20\,000\) Rysuľa sa zo všetkých síl snaží ujsť.

Môžete predpokladať, že vstup je korektný a Rysuľa sa vždy pohne práve o 1 políčko.

Formát výstupu

Po každom načítaní pozície Rysule vypíšte, ktorú časť pozemku chcete oplotiť. Keďže rohy pozemku sa dajú oplotiť z dvoch strán, pomôžeme si trikom. Zväčšíme Denisov pozemok o 1 políčko z každej strany. Krajné políčka budú “oplocovať” pôvodné Denisove pastviny. Takto navyše vieme každej časti plotu priradiť jednoznačné súradnice. Ak chcete napríklad oplotiť políčko \([1,1]\) zľava, vypíšte: 0 1.

(Dávajte si pozor na korektnosť vášho výstupu. Ak vypíšete súradnice plotu, ktorý neexistuje, alebo je už postavený dostanete "WA - Zlá odpoveď".)

Flushovanie

Programovacie jazyky štandardne používajú výstupný buffer (väčšinou 512 bajtov), a až po jeho zaplnení program vypíše jeho obsah. Flushovanie vlastne znamená vypísanie (vyprázdnenie) tohto buffera.

Vždy, keď vypíšete svoj ťah, musíte ešte flushnúť výstupný buffer. Inak sa váš ťah v skutočnosti nevypíše a nedostane sa k nášmu programu. V konečnom dôsledku potom dostanete hlášku "TLE - Prekročený časový limit".

Ako flushovať?

Ak programujete v C/C++ a používate printf(), na to aby ste flushli jeho buffer použite fflush(stdout), ak používate cout, buffer sa flushuje automaticky po vypísaní konca riadku pomocou cout<<endl. Ak programujete v Pythone, používajte print(vystup, flush=True). Ak programujete v Pascale použite flush(output)

Príklady

Input:

9 9 
5 5
6 5
7 5
8 5

... ďalších 32 riadkov

Output:

0 1
10 5
10 1

... ďalších 33 riadkov

Denis najprv postavil plot na ľavej strane rohového políčka \([1,1]\). Krava sa rozbehla doprava. Denis postavil plot napravo od políčka \([9, 5]\), kam má Rysuľa namierené. Rysuľa sa opäť pohla doprava. Po ďalších 34 ťahoch sa Denisovi podarilo oplotiť celý pozemok.

Táto úloha bola iná ako ostatné. Pomáhali ste Denisovi v jeho probléme, pričom váš program načítaval postupne pozície Rysule, a vypisoval, ktorý plot sa má postaviť. Na vyriešenie tejto úlohy sme potrebovali vymyslieť “nepriestrelnú” stratégiu, ktorá nedovolí Rysuli ujsť.

Kedy vyhrá Rysuľa

Skúsme sa na úlohu pozrieť z pohľadu Rysule. Ona sa snaží ujsť, avšak my jej staváme prekážky (ploty), cez ktoré nevie prejsť.

Základné pozorovanie je, že okrajových políčok pastviny je \(2 (r + s) - 4\) a plotov, čo musíme postaviť je \(2 (r + s)\). Vyplýva to z toho, že rohové políčko musí byť oplotené z dvoch strán.

Jedna z možných stratégií pre Rysuľu je rozbehnúť sa k najbližšiemu okraju pozemku. Ak sa jej nepodarí utiecť cez prvé okrajové políčko, na ktoré príde (lebo ho Denis stihne oplotiť), začne bežať po obvode pozemku. Ak sa jej počas toho naskytne možnosť ujsť (Denis nestihne postaviť nejakú časť plota včas), využije ju.

Predpokladajme na chvíľu, že sa Rysuľa bude správať podľa tejto stratégie. Na to, aby Denis vyhral, musí stihnúť dokončiť plot najneskôr v momente, keď Rysuľa stúpi na posledné obvodové políčko, kde dovtedy nebola. Ak by totiž aj počas nasledujúceho Rysulinho ťahu bola v plote diera, znamenalo by to, že Rysuľa cez túto dieru mohla ujsť, keď okolo nej šla.

Keďže Denis na oplotenie celého pozemku potrebuje \(2 (r + s)\) ťahov, môže vyhrať jedine v prípade, že Rysuľa bude na dobehnutie k okraju pozemku a následnú prechádzku po jeho obvode potrebovať aspoň \(2 (r+s)-1\) ťahov (keďže Denis začína, po \(2(r+s)-1\)-vom Rysulinom ťahu bude nasledovať \(2(r+s)\)-tý Denisov ťah). Ak sa Rysuľa svojím tretím ťahom dostane na okrajové políčko, prechádzku po obvode dokončí svojím \(2(r+s)-2\)-hým ťahom (obvod má \(2(r+s)-4\) políčok a prvé dva ťahy ešte nejde po obvode), takže Denis nemá šancu stihnúť postaviť plot.

To znamená, že ak sa Rysuľa vie na 3 alebo menej ťahov dostať na okrajové políčko, má zaručený spôsob ako ujsť.

Kedy vyhrá Denis

Už sme zistili, že Denis nevie vyhrať, ak Rysuľa začína 3 alebo menej políčok od okraja a je inteligentná. Stačí mu, aby začínala 4 tahy od okraja? Stačí, lebo môže hrať napríklad podľa nasledovnej stratégie:

V prvých štyroch ťahoch Rysuľa Denisovi určite neujde, keďže na štyri ťahy sa stihne dostať maximálne na okrajové políčko. Denis za tieto štyri ťahy postaví jednu časť plotu v každom rohu. Potom každé políčko bude potrebovať už len jedno oplotenie. A teda vždy keď sa Rysuľa dostaví na nejaké okrajové políčko, Denis jej tam postaví plot.

(Keďže zadanie hovorí, že vždy vieme zabrániť Rysuli ujsť, tak najmenšie pastviny majú rozmery \(9 \times 9\) a Rysuľa začína v ich strede)

Implementácia

Úloha je vcelku prísna na to čo vypíšeme. V každom ťahu musíme niečo postaviť, nemôžme postaviť plot tam kde už je postavený a tiež si musíme dať pozor aby súradnice ktoré vypisujeme boli naozaj na okraji pastviny.

Najprv musíme vyriešiť rohy pastviny. Tieto pozície budeme poznať hneď ako načítame rozmery pastviny. Vieme potom vybrať jednu časť z každého rohu (rozmyslite si prečo treba z každého), a tú oplotiť. Potom začneme v nejakom krajnom políčku, a bude oplocovať pažravo dookola. Keď sa Rysuľa dostaví na kraj, prerušíme pažravé stavanie, a postavíme plot pri políčku na ktorom sa nachádza. Ak by bola taká hlúpa a opustila kraj, tak pokračujeme v pôvodnom pažravom stavaní.

Ostáva už len vyriešiť ako si pamätať už postavené ploty? Najjednoduchšie je pouziť v C++ set alebo unordered_set (tu si musíte vytvoriť vlastnú hashovaciu funkciu), ale dajú sa tieto údaje počítať aj v obyčajnom poli.

Zložitosť

Časová zložitosť algoritmu je \(O(r + s)\) ak použijeme unordered_set alebo pole, a \(O((r+s) \cdot log(r+s))\) ak použijeme set, kedže musíme oplotiť celú pastvinu, a odpoveď ktorú časť plotu postaviť vieme zodpovedať v čase \(O(1)\). Pamäťová zložitosť tohto algoritmu je tiež \(O(r + s)\), keďže je potrebné pamätať si už postavené ploty.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.