Zadanie

Ak máte otázky ohľadom tejto úlohy píšte Kalerábovi na [email protected]

Malý Adam, ako každé leto, išiel na návštevu k jeho dedkovi. Adam k nemu chodí veľmi rád, pretože jeho dedko má na stole vždy veľkú misu s rezňami (akokoľvek čudne to znie). Samozrejme, Adam ju každé leto potajomky vykráda a tento rok nie je žiadnou výnimkou. Jeden večer, keď si už bol istý, že dedko už spí, potichu vykĺzol z izby a preplazil sa ku miske pokladov. Na jeho veľké prekvapenie tam stál dedko, ktorý si všimol, že mu rezne miznú. Dedko dal Adamovi ponuku. Adam sa môže zahrať s dedkom hru o rezne. Ak Adam vyhrá môže si nechať všetky rezne, ale ak prehrá, dedko rezne schová na vysokú skriňu, kam Adam nedočiahne.

Úloha

Dedko položil všetky rezne na stôl. Hráči sa následne budú striedať v ťahoch. Každý hráč si z kopy zoberie nejaký počet rezňov, pričom vždy začína Adam. Počet rezňov, ktoré si môžu hráči brať je väčší rovný n a menší ako m. Obidve tieto čísla určí dedko na začiatku hry. Hráč, ktorý si zoberie posledný rezeň, vyhráva. Dedko je však dobrá duša a Adamovi sľúbi, že obe čísla určí tak, že ak Adam bude hrať správne, môže vždy vyhrať. Ak počas hry nastane situácia, že počet rezňov na kôpke je menší ako n, hráč na ťahu vyhráva (zoberie zvyšok).

Formát hry

Táto úloha je interaktívna. Na prvom riadku dostane hráč čísla k, n a m, kde k je počet rezňov na kôpke a n je najmenší počet rezňov, aký si hráči môžu brať. Musia si tiež brať len počet menší ako m. Ďalej sa hráči striedajú, počínajúc Adamom. Každý hráč vypíše jedno číslo n \leq x \lt m vyjadrujúce, koľko rezňov si daný hráč berie z kopy. Hráč, ktorý si zoberie posledný rezeň, vyhráva. Na konci hry testovač vypíše adam ak vyhral Adam, inak vypíše dedko.

Aby testovanie fungovalo ako má, je nutné, aby sa po vypísaní ťahu výstup presunul z pamäte na štandardný výstup pomocou príkazu cout.flush() v C++ alebo sys.stdout.flush() v Pythone. Pre iné jazyky hľadajte ekvivalent k príkazu flush.

Limity

V prvej sade máte garantované n=1.

Príklad

               17 1 6
2
               5
4
               1
5

Na kôpke je 17 rezňov a hráči si môžu naraz brať 1, 2, 3, 4 alebo 5 rezňov. Adam si na začiatku vezme 2 rezne. Dedko nasleduje s 5timi. Adam si následne zoberie 4, a môžeme si všimnúť, že nech si dedko teraz zoberie hocikoľko rezňov, Adam vždy vyhrá.

Prvý krok, ktorý musíme spraviť k úspešnému naprogramovaniu úlohy, je zistiť víťaznú stratégiu. Následné naprogramovanie je potom relatívne priamočiare.

Stratégia

Na ukážku si zoberieme príklad zo zadania. Na kôpke je 17 rezňov a môžeme si zobrať jeden až päť rezňov. Najprv si položíme otázku: ak by na kôpke bol práve jeden rezeň, kto by vyhral? Odpoveď je jednoduchá: ten/á hráč/ka ktorý/á je na ťahu. Tak isto vyhrá hráč/ka na ťahu, ak sú na kôpke dva rezne, môže si ich proste zobrať. Rovnako to je aj pre 3, 4 a 5 rezňov. Čo sa ale stane keď je na kôpke 6 rezňov?

Keď si v tomto prípade hráč na ťahu zoberie hocikoľko rezňov, môže nastať 5 situácií. Ak si zoberie 1, ostane na kôpke 5, ak zoberie 2, ostanú 4 atď. Ak zoberie 5, na kôpke ostane jeden. Ako sme pred chvíľou ukázali, všetky z týchto možností vyhrá hráč na ťahu. Vieme teda povedať, že pozícia so 6 rezňami je prehrávajúca. Ak sa nám podarí dostať protivníka do prehrávajúcej pozície, vieme s istotou povedať, že vieme vyhrať. Taktiež vieme povedať, že pozície, z ktorých vieme dostať protivníka do prehrávajúcej pozície, sú vyhrávajúce. V tomto prípade sú to čísla 7, 8, 9, 10 a 11. Keď zo 7 zoberieme 1, z 8 zoberieme 2 atď, dostaneme protivníka na 6, čo je prehrávajúca pozícia. 12 následne bude znova prehrávajúce, pretože sa z toho dá dostať iba do vyhrávajúcej pozície. Môžeme si tu všimnúť isté pravidlo: vyhrávajúce a prehrávajúce zóny sa striedajú.

Zovšeobecnenie

Z kôpky si vždy vieme zobrať najmenej n a najviac m-1 rezňov. To znamená, že ak je na kôpke menej ako m-1 rezňov, vieme si zobrať všetky a vyhrať. Nasleduje prehrávajúca zóna. Prehrávajúca je preto, že sa z nej dá dostať iba do vyhrávajúcej. Minimálne bude mať dĺžku 1, pretože predchádzajúcich čísel je vyhrávajúcich. Ak je ale n väčšie ako 1, bude aj prehrávajúca zóna väčšia, pretože sa z nasledujúcich čísel nedá dostať do menších čísel tej istej prehrávajúcej zóny.

Z tohoto si vieme odvodiť, že tieto vyhrávajúce a prehrávajúce zóny sa striedajú, veľkosť vyhrávajúcej zóny je m-1 a veľkosť prehrávajúcej zóny je n.

Optimalizácie

Je lákavé si ručne odrátať všetky výherné a prehrávajúce zóny. Avšak pri veľkom množstve rezňov a malom m bude náš program veľmi pomalý. Toto sa však dá vyriešiť viacerými spôsobmi. Aktuálna kopa rezňov sa dá zmodulovať (n+m-1), pretože to reprezentuje zvyšok zóny po odstránení dvojíc výherná + prehrávajúca. Tento spôsob je použitý aj vo vzorovom kóde.

Ďalší prístup by bol predrátať si pre každé číslo či je vyhrávajúce alebo prehrávajúce, a následne už len vracať toto z poľa podľa toho ako hrá oponent. Toto nám však zvýši pamäťovú zložitosť, keďže si musíme pamätať každý ťah.

Vzorové riešenie

def tahaj(k, n, m):
    velkost_vyhravajucej_zony = m - 1
    velkost_prehravajucej_zony = n

    # Optimalizácia používajúca modulo
    i = k - (k % (velkost_vyhravajucej_zony + velkost_prehravajucej_zony))
    vyhravam = False
    while i < k:
        if not vyhravam:
            i += velkost_vyhravajucej_zony
        else:
            i += velkost_prehravajucej_zony
        vyhravam = not vyhravam

    if not vyhravam:  # Nikdy by sme sa nemali dostať do prehrávajúcej zóny
        raise ValueError
    else:
        return max(n, k % (velkost_vyhravajucej_zony + velkost_prehravajucej_zony))


reznov, najmenej, najviac = list(map(int, input().split()))

while True:
    tah = tahaj(reznov, najmenej, najviac)
    print(tah)
    reznov -= tah
    inp = input()
    try:
        reznov -= int(inp)
    except ValueError:
        break

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ť.