4. Párty žiab vzorové riešenie

5 -1

ANO
2 3
3 5
4 5
5 1

9 3

ANO
1 2
3 2
4 5
6 5
7 8
9 8
8 5
2 5

Riešenie bez žaby Michala

Pozrime sa najprv na ľahšiu úlohu, v ktorej sa žaba Michal nenachádzal. Našou úlohou je teda iba zhromaždiť všetky žaby na jednom lekne.

Na začiatok sa pokúsme vyriešiť úlohu s malým počtom žiab. Napríklad, ak máme iba jednu žabu, úloha je ľahká, pretože všetky (jedna) žaby sú spolu na jednom lekne. Pridajme teda aj druhú žabu. Problém je stále jednoduchý, stačí ak žaba z prvého lekna skočí na druhé lekno a môže začať párty. Do takejto situácie pridajme na začiatok tretie lekno. Situácia bude teda vyzerať nasledovne.

Všimnime si, že keďže na pravom lekne sedia dve žaby, vedia skočiť na vzdialenosť 2. Čím skočia presne na prvé lekno, kde ich čaká tretia žaba. Tieto tri žaby teraz vedia skákať skokom dĺžky 3 a keď na pravej strane pridáme štvrtú žabu, tá bude od nich vzdialená presne o 3 lekná. Potom vieme naľavo pridať piatu žabu, ktorá je vzdialená o 4 lekná a takto nastriedačku pokračovať ako dlho budeme chcieť.

Postup skákania je teda pomerne jednoduchý. Začneme so žabou, ktorá sedí na strednom lekne. Tá skočí na susedné lekno, následne obe žaby skočia opačným smerom na lekno vo vzdialenosti 2, kde sa stretnú s treťou žabou, opäť zmenia smer a skočia na lekno, vzdialené 3. Po každom skoku teda zmenia smer, ktorým skáču a veľkosť ich skoku sa zväčší o 1.

Pozor si musíme dať iba v prípade, keď je žiab párne veľa. V takom prípade sú totiž dve stredné žaby. Môžeme si vybrať ľubovoľnú z nich, potom si však musíme dať pozor, aby prvý skok išiel do správneho smeru – tam kde je viac žiab.

Takéto riešenie vieme implementovať pomerne jednoducho. Budeme si pamätať, na ktorom lekne stojí naša kôpka žiab (na začiatku je to lekno \(\frac{n+1}{2}\)), koľko ich na tomto lekne je (na začiatku 1), a teda aký veľký skok vedia robiť a smer, ktorým majú skákať. Smer skoku v podstate určuje, či chceme pri počítaní lekna, na ktoré skočia dĺžku ich skoku pričítavať alebo odčítavať. Na to môžeme použiť buď hodnoty true a false alebo aj \(1\) a \(-1\).

Riešenie so žabom Michalom

Pribudla nám žaba Michal, ktorý nechce, aby po ňom zvyšné žaby skákali. Skúsme sa zamyslieť nad tým, ako nám môže pomôcť riešenie ľahšej podúlohy. Existuje v pôvodnom riešení žaba, na ktorú nikto nikdy neskočí? Áno, žaba ktorou sme začínali, teda sa nachádzala v strede, bude neustále navrchu. Ak by teda žaba Michal bol v strede, úlohu by sme vedeli riešiť tým istým spôsobom.

Ako však vyriešiť prípady, keď Michal nebude v strede? Predstavme si, že Michal sedí na úplne prvom lekne. Vynechajme na zatiaľ toto lekno a pozrime sa na zvyšných \(n-1\). Medzi nimi sa Michal nenachádza, takže ak chceme, aby sa tieto žaby stretli, môžeme použiť riešenie ľahšej podúlohy. Naviac si všimnime, že použitím tohto postupu skončia žaby na jednom z krajných leknien, pretože skáču od stredu do krajov. A naviac, vieme ovplyvniť aj to, na ktorom kraji skončia. Stačí ak správne zvolíme smer prvého skoku – pre nepárne \(n\), ak chceme skončiť na ľavom kraji, musíme najskôr skákať doprava, v opačnom prípade musíme najskôr skočiť doľava.

Z tohto pozorovania nám ale vyplýva, že zvyšných \(n-1\) žiab vieme zhromaždiť na ľavom krajnom lekne, na lekne, ktoré je druhé v poradí, lebo na prvom sedí Michal. A keď sú už na druhom lekne všetky zvyšné žaby, Michal na nich jednoducho vyskočí.

A čo sa stane ak bude Michal na druhom lekne? Potom jedna možná postupnosť skokov je najskôr dostať \(n-2\) žiab, ktoré sú napravo na tretie lekno v poradí. Toto vieme spraviť bez problémov, lebo medzi nimi Michal nie je. Následne Michal skočí na prvé lekno a spolu so žabou, ktorá sa na ňom nachádza skočia na lekno tri, ktoré je vzdialené 2.

Nuž a teraz si riešenie zovšeobecnime. Zoberme žabu Michala a začnime s ním skákať nastriedačku do oboch strán tak ako v prvom riešení. V nejakom momente budeme musieť zastať, pretože Michal (so všetkými žabami pod ním) nebude môcť skočiť ďalej, lebo by skočil mimo lekien. To ale znamená, že smerom, ktorým chce skočiť už na leknách nie sú žiadne ďalšie žaby. Všetky pozbieral predchádzajúcimi skokmi. A naviac, v opačnom smere sa na každom lekne nachádza jedna žaba, pretože to sú lekná, na ktoré Michal ešte nestihol skočiť.

My však cheme všetky žaby na jednom lekne. Na tento úsek lekien, na ktorých sedia žaby (vrátane lekna s Michalom a žabami pod ním) vieme použiť predchádzajúci algoritmus, pričom budeme chcieť, aby sa žaby stretli na lekne, na ktorom stojí Michal. Tu však nastane problém, pretože potom predsa nejaké žaby skočia na Michala.

Uvedomme si však, že nám na poradí, v ktorom tieto skoky budeme robiť nezáleží. Môžeme teda najskôr nechať skákať žaby, ktoré Michal počas svojich skokov nestretne a až potom začať skákať s Michalom. Takto sa všetci stretnú na spoločnom lekne a Michal bude navrchu.

Ostáva nám takéto riešenie naprogramovať. Jeden možný spôsob je skákať s Michalom a ukladať si skoky, ktoré robí. Pomocou toho zistíme, na ktorom lekne sa majú žaby stretnúť, odsimulujeme skoky ostatných žiab, pričom ich skoky naozaj vypisujeme a až potom vypíšeme skoky s Michalom.

Druhá možnosť je dopredu vypočítať, na ktorom lekne sa žaby stretnú. To vieme robiť aj jednoduchým skúšaním každého lekna. Pre toto lekno totiž bude musieť platiť, že Michal sa na začiatku nachádza v strede medzi ním a jedným z krajov jazera. Následne vieme simulovať obe skákania.

V oboch prípadoch bude časová zložitosť takéhoto riešenia \(O(n)\) a pamäť vie byť pri správnej implementácii dokonca konštatná.

#!/usr/bin/env python3
n, m = map(int, input().split())

m = max(m, -m) # ak m = -1 tak sa budeme tvarit, ze m = 1, lebo sa nam nechce pisat podmienku
m -= 1 # cislujeme od nuly

print("ANO")

if n == 1:
    # ak je len jedna zaba, uz je party
    exit()

prikazy = []
prikazyM = []

kde = m
smer = -1
dlzka = 1
if m < n - m - 1:
    smer = 1
    
while kde + smer * dlzka < n and kde + smer * dlzka >= 0:
    prikazyM.append("{} {}".format(kde + 1, kde + smer * dlzka + 1))
    kde = kde + smer * dlzka
    dlzka += 1
    smer *= -1

if dlzka == n:
    # michal uskakal vsetky
    print("\n".join(prikazyM))
    exit()
    
kdeparty = kde
    
dlzka = 1
if m > kde:
    if kde % 2 == 1:
        smer = 1
    else:
        smer = -1
    kde = kde // 2
else:
    if (n - kde) % 2 == 1:
        smer = 1
    else:
        smer = -1
    kde = (n - kde) // 2 + kde

while kde != kdeparty:
    prikazy.append("{} {}".format(kde + 1, kde + smer * dlzka + 1))
    kde = kde + smer * dlzka
    dlzka += 1
    smer *= -1
    
print("\n".join(prikazy))
print("\n".join(prikazyM))
exit()