Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Máriovi Lipovskému na

Párty sa skončila. Väčšina zúčastnených rýchlo osedlala svoje vesmírne veľryby a okamžite zmizla. Vo vyprázdnenej miestnosti však zostalo ešte zopár čudákov, ktorí nemajú veľryby. Väčšina z nich je síce zo Zeme, no pochádzajú z rôznych časov, krajov sveta a rôznych spoločenských vrstiev a vôbec sa nepoznajú. Hanblivo sa obzerajú, pomaličky sa presúvajú k východom a aj oni by sa chceli čo najrýchlejšie vytratiť a ísť spať späť domov.

Tieto historické, terajšie a fiktívne osobnosti sú ale bohužiaľ odkázané na hromadnú dopravu. Hromadná doprava funguje ako sieť teleportov a strojov času, dá sa presúvať len dvoma smermi – v priestore a čase. Samotné cestovanie trvá pomerne krátko. Cestovatelia na jednej stanici naskočia do teleportu alebo do stroja času, chvíľku sa vznášajú mimo vesmíru a dopadnú do ďalšej stanice. Medzi stanicami je to teda iba na skok.

Aby prepravná spoločnosť presvedčila čo najviac cestovateľov používať ich prepravné zariadenia, na každej stanici rozdávajú cukríky.1 Na rôznych staniciach ich rozdávajú v rôznom množstve a cestovatelia sa postupom času naučili, koľko cukríkov dostanú na ktorej stanici. Vždy pred cestovaním si preto spočítajú, kadiaľ pôjdu tak, aby boli doma čo najrýchlejšie a zároveň získali čo najviac cukríkov.

Úloha

  1. (5 bodov) Na obrázku je plán časopriestorových staníc. Každé číslo predstavuje počet cukríkov, ktoré cestovateľ dostane na danej stanici. Pre obyvateľa každého domčeka, hradu, planéty… zistite, koľko najviac cukríkov vie nazbierať, ak začína v ľavom hornom rohu a chce sa dostať domov – príslušný pravý dolný roh. Počas celej cesty sa môže pohybovať len smerom dole a doprava – najkratšou možnou cestou.

    Okrem odpovede nám popíšte aj postup, akým ste dospeli ku vašim výsledkom. Prečo ste si istí, že vaše výsledky sú správne?

  1. (3 body) Ako by sa zmenila situácia, ak by boli všetky obydlia ešte o kúsok ďalej? Opäť zistite, aký najväčší počet cukríkov sa dá nazbierať cestou z ľavého horného rohu do každého z pravých dolných.

    Všimnite si, že až na poslednú pridanú diagonálu sú čísla na obrázkoch rovnaké. V popise svojho riešenia sa preto môžete odvolávať na to, čo ste vypočítali v časti a). Opäť svoje riešenie odôvodnite.

  1. (5 bodov) Hoci teraz každý vie, na koľko cukríkov sa môže tešiť, nikto stále netuší, ako presne má tie cukríky pozbierať. Na záver teda pre každé z 11 obydlí z druhého obrázku zistite, akou cestou má jeho obyvateľ ísť, aby nazbieral čo najviac cukríkov.

    Každú cestu popíšte ako postupnosť písmen P,D podľa toho, či je potrebné ísť vPravo, alebo Dole (cesta PPDDP napríklad stručne popisuje pohyb po políčkach s číslami: 42-5-6-4-9-7, a nie je úplná). Napíšte nám aj čo najviac o postupe, ktorým ste najvýhodnejšie cesty zistili.

  2. (2 bod) Dali by sa vaše postupy z predošlých úloh použiť, aj keby ste dostali mapku rozmerov \(80\times 80\)? Dokázali by ste túto úlohu riešiť všeobecne pre ľubovoľne veľkú mapu a pre ľubovoľné čísla na nej?

    Skúste odhadnúť, koľkokrát dlhšie by vám trvalo zisťovanie výsledkov na mapke \(80\times 80\) oproti mapke z podúlohy a).


  1. Pôvodne plánovali zaviesť cestovanie zadarmo, ale tento nápad stroskotal, keď si spočítali príjmy a výdaje.

Prvé riešenie, ktoré vás napadne

Pre obyvateľov najspodnejšieho a najpravejšieho domčeka je najlepšia cesta zjavná, lebo majú na výber iba jednu možnosť – ísť stále dole alebo stále doprava. Cesty vieme zapísať ako DDD…D, PPP…P, keď použijeme formát ako v podúlohe c), kde D je dole, P je vpravo.

Najlepšia cesta do druhého domčeka odspodu a do druhého sprava sa hľadá trošku ťažšie, no tiež tu nie je veľa rôznych možností.1 Do každého z týchto dvoch domčekov sa dá dostať 9 rôznymi cestami. Napríklad do toho druhého sprava pôjdeme stále doprava a jedenkrát sa počas cesty rozhodneme zísť dole.

Pre ďalšie domčeky by sme vedeli nájsť najlepšiu cestu podobným spôsobom. Vyskúšali by sme všetky možné cesty a z nich by sme vybrali ku každému domčeku tú, kde získame najviac cukríkov. Ale ako to vieme spraviť? Ako vieme zabezpečiť, že žiadnu cestu nevynecháme a žiadnu nebudeme počítať dvakrát? Tu nám pomôže práve zápis cesty ako v podúlohe c).

Ako spočítať všetky cesty

  • Začíname na ľavom hornom políčku, máme \(42\) cukríkov a prešli sme cestu dĺžky \(0\).

  • Môžeme sa rozhodnúť ísť doprava, to budeme mať \(42+5=47\) cukríkov, prejdená cesta je P.
    Môžeme sa rozhodnúť ísť dole, to budeme mať \(42+7=49\) cukríkov, prejdená cesta je D.
    Podarilo sa nám spočítať všetky cesty dĺžky \(1\).

  • Ako vieme spočítať všetky cesty dĺžky \(2\)? Z konca každej cesty dĺžky \(1\) sa rozhodneme ísť vpravo alebo dole a dostaneme cesty:
    PP \(47+6=53\), PD \(47+7=54\), DP \(49+7=56\), DD \(49+6=55\)

  • Opakovaním by sme dostali všetky cesty dĺžky \(3,4,\dots\)

Vďaka tomu, že sú domčeky na diagonále, sú všetky rovnako ďaleko od ľavého horného rohu. Teda na to, aby sme sa dostali do ľubovoľného domčeka potrebujeme spraviť presne 9 krokov2. Pre vyriešenie úlohy by sme zopakovali postup \(9\)-krát a na záver vieme zistiť, ktorá cesta vedie ku ktorému domčeku, napríklad z počtu P, D v jej zápise 3. Samozrejme, praktickejšie by bolo si ku každej ceste písať políčko, na ktorom skončila.

Po každom kroku sa nám počet doterajších ciest zdvojnásobí, takže vieme, že po \(9\) krokoch budeme mať spočítaných \(2\cdot2\cdot\dots\cdot2 = 2^9 = 512\) ciest. Okrem toho sme doteraz museli vypočítať 1 cestu dĺžky 0, 2 cesty dĺžky 1, 4 cesty dĺžky 2 atď., teda \(1+2+4+8+16+32+64+128+256 = 512-1\)4.

Vyzerá to ako veľa práce. Za pár hodín sa to ale dá spraviť a vyriešite hneď aj podúlohu c). Pokiaľ by ste dostali tabuľku veľkosti \(80\times80\), na konci by ste museli spočítať \(2^{79}\) ciest a ak k tomu prirátame aj všetky doterajšie kratšie cesty, \(2^{80}-1\) a trvalo by vám to \(2^{70}\)-krát dlhšie.

Takýto postup, hoci môže trvať dlho, je v princípe dobrý, lebo ním viete získať zaručene správne riešenie.

Ak máte funkčný postup a dokážete prinútiť počítač, aby ho spravil za vás, viete 3 hodiny počítania zmeniť na 20 minút programovania a pár sekúnd behu programu. Bohužiaľ, pri vstupe \(80\times80\) by vám veľmi nepomohli ani dnešné počítače. Dokážu síce spraviť niekoľko miliárd operácií za sekundu, ale \(2^{80} \cong 10^{24}\), teda program by stále bežal rádovo milión milárd sekúnd.

Ak vám už chvíľku trhá kútikmi úst, že prečo to robíme tak zdĺhavo, tak je dobre. Toto jednoduché riešenie skutočne skrýva návod k optimálnemu, rýchlemu riešeniu.

Nechceme počítať nič, čo nepotrebujeme

Možno ste si všimli, že cesty PD a DP skončia obe na rovnakom políčku, no po ich prejdení získame rôzny počet cukríkov – 54 a 56. Keby sme hľadali cesty dĺžky 3 v predošlom postupe, pokračovali by sme z oboch ciest (DP, PD) dole aj vpravo. Cestami DPD, PDD (aj DPP, PDP) sa potom dostaneme na to isté políčko a bez toho, aby sme sa pozerali na plánik vieme, že cesta DPD bude výhodnejšia ako PDD. Cesty začínajúce PD teda nikdy nebudú najvýhodnejšie, lebo rovnaké cesty začínajúce DP budú výhodnejšie. Keď vieme, že nám stačí pamätať si len najvýhodnejšiu cestu, ktorá končí na danom políčku, predošlý postup by sme upravili takto:

  • Cesta dĺžky 0 je len jedna, získame 42 cukríkov.

  • Cesty dĺžky 1 sú 2 – P,D – a končia na 2 rôznych políčkach – políčko s 5, políčko so 7

  • Cesty dĺžky 2 sú 4 – PP, PD, DP, DD – ale končia len na 3 políčkach, ktoré tvoria diagonálu. Pre každé z týchto políčok vyberieme najlepšiu cestu a zostanú nám cesty: PP, DP, DD.

  • Cesty dĺžky 3 budeme počítať už len \(2 \times 3 = 6\). Dostávame 6 ciest, ktoré končia na 4 políčkach a teda opäť vyberieme len tie najlepšie pre každé políčko na diagonále.

Týmto spôsobom vieme postupne spočítať najlepšiu cestu pre každé políčko tabuľky. Ako ,,vedľajší produkt’’ sa dozvieme na záver aj najlepšie cesty do každého domčeka.

Po 9 krokoch vieme 10 najlepších ciest – jednu do každého domčeka. Keď pridáme 1 riadok/diagonálu mapky, ako v podúlohe b), máme z každého z 10 políčok na výber z 2 možností, kam pokračovať, teda existuje 20 ciest do 11 políčok. Vyberieme si len tú najlepšiu pre každý domček.

Na predošlý postup sa vieme pozrieť aj z iného uhla. Predpokladajme, že máme spočítané cesty dĺžky 9. Teda najlepšie cesty do koncových políčok v úlohe a). Ak chceme vyriešiť úlohu b), stačí sa pozrieť z každého nového políčka hore a doľava a vybrať si lepšiu cestu, po ktorej do neho vieme prísť. Najväčší počet cukríkov, ktorý vieme získať na políčku v riadku \(r\) a v stĺpci \(s\) si označíme ako \(best[r][s]\) a vieme to vypočítať ako: \[best[r][s] = \max(best[r-1][s], best[r][s-1]) + mapa[r][s]\] \(best\) z políčok mimo mapky si môžeme definovať ako 0 a potom bude sedieť, že \(best[1][1] = \max(0,0) + 42\), \(best[1][2] = max(0,42)+5\), atď.

Ak viedli viaceré cesty na jedno políčko a vybrali sme si tú najlepšiu, vyberali sme si vždy z dvoch ciest – zhora a zľava. Počas výpočtu sme teda pre každé políčko tabuľky zvažovali najviac 2 cesty. Políčok bolo \(\frac{10\times10 - 10}{2}+10 = 55\)5 v a). Celkovo sme teda zvážili približne \(10^2\) ciest. Vieme tak, že ak by sme dostali tabuľku \(80\times80\), tiež sa pri počítaní najlepšej cesty pre každé políčko rozhodujeme len medzi 2 možnosťami a zvažovali by sme približne \(80^2\) ciest. Výpočet takejto úlohy by nám trval približne 64-krát dlhšie.

Máme postup, ale aj tak sme leniví a nechce sa nám sčítavať veľa čísel

Keď už máme postup upravený tak, že sa stačí pozerať na 2 políčka, hore a vľavo, môžeme úlohu vyriešiť napríklad v exceli:

  • Ručne opíšeme alebo si skopírujeme z pdf zadaní tabuľku s číslami. Povedzme, že ľavý horný roh umiestnime do bunky B2.

  • Tabuľku s výsledkami umiestnime napravo, s ľavým horným rohom v bunke O2. Necháme ju zatiaľ prázdnu.

  • Políčka okolo druhej tabuľky vyplníme nulami: hodnoty \(best\) mimo tabuľky.

  • Do políčka O2 vložíme rovnicu =MAX(O1,N2)+B2, čo zodpovedá rovnici pre best.

  • Potiahnutím za pravý dolný roh O2 roztiahneme rovnice na ďalšie políčka

Voilá. Excel6 to spočítal za nás. Najskôr počíta políčka, ktoré vie spočítať: ľavý horný roh. Potom počíta políčka, ktoré sú na nich závislé – čísla v druhom stĺpci, prvom riadku a v prvom riadku, druhom stĺpci. Potom čísla vo vzdialenosti 3. A zvyšok tabuľky podobne.

Z tejto tabuľky je aj vidno, kadiaľ sme na ktoré políčko prišli, a teda vieme zistiť cesty ku každému domčeku ,,odzadu’’.


  1. V porovnaní s cestami ku zvyšným domčekom.

  2. V podúlohe b) 10 krokov.

  3. Každá cesta, ktorá vedie napríklad do tretieho domčeka zhora, musí obsahovať presne \(3\times\)D.

  4. To, že \(1+2+4+\dots+2^n = 2^{n+1}-1\) si môžete dokázať napríklad matematickou indukciou, alebo sa môžete nechať presvedčiť úžasným obrázkom.

  5. Zoberieme tabuľku \(10\times10\), odpočítame diagonálu v strede, zoberieme polovicu zvyšku tabuľky a pripočítame diagonálu v strede.

  6. Calc, alebo ľubovoľný tabuľkový editor.

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