*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.¹ 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).