Zadanie

Po mnohých ďalších mesiacoch plavby sa Magalhãesova flotila konečne vrátila naspäť do rodného Portugalska. So sebou si námorníci priniesli aj nemalý poklad. Po zakotvení narazili v prístave na talianskeho vynálezcu menom Gianetta (čítaj Žaneta), ktorý ich zaujal svojim vynálezom. Pomocou neho mohli moreplavci investovať a zhodnocovať svoje prinesené zlaté mince, podobne ako na dnešnej burze. Bystrí chlapci si však všimli v Gianettovom vynáleze chybičku. Vyzerá to, že vďaka nej môžu pri správnom rozdelení mincí získať neúmerné bohatstvo.

Na začiatok moreplavci umiestnia na tri kôpky postupne a, b, c mincí, kde a,b,c2017 sú kladné celé čísla. Vynález umožňuje v jednom kroku vykonať jednu z nasledujúcich operácií:

  • Moreplavci si vyberú kôpku, na ktorej je párny počet mincí. Vynález z nej zoberie všetky mince a po polovici z nich dá na zvyšné dve kôpky.

  • Moreplavci si vyberú kôpku, na ktorej je nepárny počet mincí a zároveň aspoň 2019 mincí. Vynález z nej zoberie 2019 mincí a na zvyšné dve kôpky pridá po 1010 mincí.

Predpokladajme, že vo vynáleze je dostatok mincí navyše. Nájdite všetky usporiadané trojice (a,b,c), pre ktoré po nejakom konečnom počte ťahov moreplavci vedia dostať na niektorej kôpke aspoň 20192020 mincí.

Môžeme si všimnúť, že po každej operácii celkový počet mincí ostane rovnaký, alebo sa zvýši. Ak by sa nám vždy podarilo zvýšiť počet mincí, raz budeme mať dosť veľa mincí na to, aby na niektorej kôpke bolo aspoň 20192020 mincí. V prípade ak bude na každej kôpke len 2017 mincí, tak nevieme urobiť žiadnu operáciu a skončili sme. Ak bude na niektorej kôpke viac ako 2017 mincí, už vieme robiť nejaké operácie a ukážeme si, že dokonca vždy budeme vedieť pridať ďalšiu mincu.

Odteraz nech je na kôpkach spolu aspoň 32017+1 mincí. Vždy vieme spraviť nejaký ťah, lebo ak je na všetkých kôpkach nepárny počet mincí, na tej najväčšej musí byť aspoň 2019 mincí a použijeme na ňu operáciu (2). Ak je na niektorej kôpke párny počet mincí, vieme ju rozdeliť na zvyšné dve kôpky operáciou (1). V takomto prípade dostaneme na jednej kôpke 0 mincí a kým budeme robiť len operácie (1), stále bude na niektorej kôpke 0 mincí. Keď použijeme operáciu (2), zvýšime celkvý počet mincí a môžeme začať odznova. Preto stačí dokázať, že keď sme v stave, kde je na niektorej kôpke 0 mincí, vieme spraviť niekoľko ťahov (1) tak, aby sme potom mohli spraviť ťah (2).Počty mincí na dvoch nenulových kôpkach označíme A,B, kde A je ten väčší počet, AB.

Ak A je nepárne, vidíme, že A2019. Stačí keď použijeme operáciu (2) na kôpku A, teda sme pridali celkovo 1 mincu.

Ak je A párne a B je nepárne, pozrime sa ešte, aké veľké je B. Ak B2019, tak použijeme naň operáciu (2) a zvýšime celkový počet mincí. V opačnom prípade (označme A=2K) kôpku A rozdelíme na dve polovice po K. Počty mincí na kôpkach budú K a B+K. Keďže B mohlo byť najviac 2017, tak A bolo aspoň 22017+1, teda K je aspoň 2018. Spolu máme nepárny počet mincí (A+B), takže na niektorej kôpke je nepárny počet mincí. Na oboch kôpkach (K aj B+K) je aspoň 2018 mincí, takže na tej nepárnej je aspoň 2019 mincí, môžeme na ňu použiť operáciu (2).

Ak je A aj B párne, jednoducho kôpku na ktorej je menej mincí vždy rozdelíme na dve polovice Takto sa nám vždy zmenší počet mincí na menšej kôpke, takže raz sa musíme zaseknúť. V takom prípade bude na oboch kôpkach nepárny počet mincí, takže na väčšiu z nich použijeme operáciu (2).

Keď na začiatku bolo na kôpkach (2017,2017,2017) mincí, tak moreplavci nevedia dostať na žiadnej kôpke 20192020 mincí. Vo všetkých ostatných prípadoch vedia, pretože vždy vedia pridať 1 mincu a raz, keď bude všetkých mincí dosť veľa, tak na niektorej kôpke bude musieť byť aspoň 20192020 mincí.

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