3. Ambiciózne múzeá vzorové riešenie

Zadanie

Novinka: táto úloha je rozdelená na niekoľko na seba nadväzujúcich sád, za ktoré viete dokopy získať 100 bodov. Zatiaľ máte k dispozícii iba zadania prvej sady. Na získanie zadaní ďalšej sady je potrebné odovzdať riešenia tej predchádzajúcej.

Hocikedy v priebehu kola môžete odovzdať vaše aktuálne riešenie. My vám ho v priebehu pár dní opravíme a pošleme späť aj s komentármi. Ak sa vám podúlohy podarilo vyriešiť správne, dostanete ďalšie zadania. Ak vaše riešenie nebolo správne, nič sa nedeje. V komentári vám skúsime poradiť kde nastala chyba a vy ju môžete opraviť a poslať znova až kým nebudete úspešní.

Veríme, že takto sa vám podarí vyriešiť viac podúloh a teda sa aj viac naučíte. Nabojte sa nám teda poslať aj rozpracované riešenie, alebo také, ktorým si nie ste úplne istí. Nehrozí vám žiadna penalizácia a môžete dostať dobrú radu. Odporúčame však úlohu riešiť priebežne.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Marianke na [email protected]

Sem-tam je čas na zmenu, pomyslel si Samko, keď dostal nápad otvoriť si múzeum Kurióznych Starodávnych Predmetov. Takéto múzeum sa skladá z niekoľkých vitrín, v ktorých sú vystavené kuriozity. Vitríny sú očíslované od 1 po \(n\) (počet vitrín v múzeu) a v každej môže byť nanajvýš jedna kuriozita.

Do múzea chodia návštevníci a čím viac kuriozít v ňom je, tým sú spokojnejší. Samko preto usilovne pracuje na rozširovaní svojej zbierky. Vždy keď získa novú kuriozitu, uloží ju do voľnej vitríny. V nejakom momente sa však stane, že naplní všetky vitríny a viac sa mu ich do budovy už nezmestí. Bude preto musieť kúpiť priestory s väčším počtom vitrín a všetky staré kuriozity tam pracne preniesť.

Pri rozbiehaní takétoho vážneho biznisu je dôležité sledovať tok peňazí a práve s výdavkami sa Samko trápi. Beh múzea totiž obnáša nasledovné náklady. Vždy keď Samko získa novú kuriozitu a uloží ju do vitríny, zaplatí 1 peniaz (za jej kúpu). Navyše, musí platiť za nákup nových, väčších budov. Kúpenie budovy, do ktorej sa zmestí \(n\) vitrín ho stojí \(n\) peňazí. No a nakoniec, stojí ho aj prenášanie kuriozít do novej budovy, za každú prenesenú kuriozitu zaplatí \(1\) peniaz.

Všimnite si, že pri kúpe novej budovy do nej Samko musí preniesť všetky staré kuriozity a navyše, za starú budovu nedostane späť žiadne peniaze (to viete, inflácia, opotrebovanie a tak).

Interaktívna pomôcka

Pripravili sme pre vás webové prostredie, ktoré simuluje Samkovo múzeum – najmä jeho výdavky. Odporúčame ho využiť pri riešení podúloh z prvej sady.

Sada úloh 1 – Stratégie kupovania budov

Samko chce zozbierať všetky kuriozity sveta, nevie však koľko ich je, môže ich byť 10 alebo \(100\,000\,000\). Zistí to až v momente, keď získa tú poslednú z nich (daný predmet je totiž kuriózny tým, že je poslednou kuriozitou sveta, ktorú Samko nevlastní). Dovtedy sa jeho múzeum postupne rozrastá a on chce, samozrejme, optimalizovať svoje výdavky. Vymyslel si preto rôzne stratégie, podľa ktorých nakupuje nové priestory. Pomôžte mu ich ohodnotiť a navhrnite vlastnú, ešte lepšiu.

1. (12 bodov) Samkova prvá stratégia na rozbiehanie biznisu je, že vždy keď sa mu naplní priestor v múzeu, kúpi si novú budovu, do ktorej sa zmestí o 10 vitrín s kuriozitami viac. Na začiatku nevlastní žiadnu budovu, začne teda nákupom budovy veľkosti 10.

   Predstavte si, že na svete je 100 kuriozít. Koľko peňazí Samko zaplatí, kým ich všetky získa? Popíšte, aj ako ste danú sumu vypočítali.

   Pre aké počty kuriozít sveta sa táto stratégia nehodí, a pre aké je naopak dobrá?

2. (12 bodov) Ďalšia Samkova stratégia je podobná, akurát po naplnení kúpi priestor o \(1\,000\,000\) vitrín väčší. Na začiatku nevlastní žiadnu budovu.

   Predstavte si, že na svete je \(10\,000\,000\) kuriozít. Koľko peňazí Samko zaplatí, kým ich všetky získa? Popíšte, aj ako ste danú sumu vypočítali.

   Pre aké počty kuriozít sveta sa táto stratégia nehodí, a pre aké je naopak dobrá?

3. (25 bodov) Samko by chcel, aby ste mu navrhli vlastnú stratégiu, ktorá bude vhodná bez ohľadu na to, koľko kuriozít sa na svete nachádza.

   Popíšte, ako by vaša stragégia fungovala, a koľko peňazí by Samko zaplatil, ak by na svete bolo 100 kuriozít, a ak by ich bolo \(10\,000\,000\).

   Vysvetlite, prečo je vaša stratégia lepšia ako dve Samkove popísané v podúlohách a) a b).

Sada úloh 1 – Stratégie kupovania budov

Podúloha a)

Podúlohu si pri počítaní, koľko peňazí Samko zaplatí, kým vyzbiera všetky kuriozity sveta, vieme rozdeliť na 3 časti:

• koľko peňazí zaplatí za všetky kuriozity sveta
• koľko peňazí zaplatí za múzeá s vitrínami
• koľko peňazí zaplatí za presun kuriozít zo starého do nového múzea

Vieme, že na svete je iba \(100\) kuriozít, takže ak bude chcieť Samko nakúpiť všetky kuriozity sveta, minie za ne \(100\) peňazí.

Na to, aby niekde kuriozity uložil, si bude kupovať múzeá s vitrínami. Zo zadania vieme, že si Samko postupne kupoval múzeá s \(10, 20, \ldots, 100\) vitrínami – začal s múzeom s \(10\) vitrínami a postupne si kupuje múzeá, kde je o \(10\) vitrín viac od predchádzajúceho múzea. Nakoniec skončí s múzeom so \(100\) vitrínami, lebo väčšie múzeum už nepotrebuje. Za múzeá preto zaplatí \(10 + 20 + \cdots + 100 = 550\) peňazí.

Pri tom, ako si kupuje nové múzeá, musí kuriozity presúvať. Vždy presunie všetky kuriozity z predchádzajúceho múzea do nového, avšak z posledného múzea už kuriozity nepresúva. Preto zaplatí \(10 + 20 + \cdots + 90 = 450\) peňazí. Dokopy Samko zaplatí \(100 + 550 + 450 = 1100\) peňazí.

Takáto stratégia sa hodí pre menšie počty kuriozít, pretože Samko nekupuje zbytočne veľké múzeá s veľa vitrínami, ktoré nakoniec nevyužije naplno. Pre vysoké počty sa naopak nehodí, lebo by príliš často musel kupovať nové múzeá a presúvať kuriozity.

Podúloha b)

V podúlohe b) vieme postupovať rovnako. Keďže je všetkých kuriozít sveta \(10\,000\,000\), tak zaplatí \(10\,000\,000\) peňazí. Pri zväčšovaní múzeí vždy o \(1\,000\,000\) vitrín zaplatí \(1\,000\,000 + 2\,000\,000 + \cdots + 10\,000\,000 = 55\,000\,000\) peňazí. Keď bude kuriozity presúvať, tak zaplatí \(1\,000\,000 + 2\,000\,000 + \cdots + 9\,000\,000 = 45\,000\,000\) peňazí. Dokopy teda zaplatí \(10\,000\,000 + 55\,000\,000 + 45\,000\,000 = 110\,000\,000\) peňazí.

Takáto stratégia sa hodí pre väčšie počty kuriozít, pretože si Samko kúpi veľké múzeum s veľa vitrínami a nemusí sa tak často sťahovať a presúvať kuriozity. Pri malých počtoch kuriozít si Samko kúpi príliš veľké múzeum, ktoré sa zaplní iba čiastočne, takže naň minie zbytočne veľa peňazí.

Podúloha c)

Neexistuje iba jedna lepšia stratégia ako Samkova. Stratégií je veľa a sú rôzne efektívne. Do vzorového riešenia, som vybrala jednu z najefektívnejších, s ktorými sa vieme stretnúť. Jej princíp spočíva v tom, že na začiatku si kúpime múzeum s \(1\) vitrínou a každé ďalšie múzeum bude mať dvakrát toľko vitrín ako predcházdajúce. Takže kupované múzeá by mali \(1, 2, 4, 8, 16, \ldots\) vitrín, inak povedané \(2^0, 2^1, 2^2, 2^3, 2^4, \ldots\) vitrín. Táto stratégia nefunguje iba striktne s číslom \(2\). Môžeme začať aj napríklad s múzeom s \(5\) vitrínami a každé ďalšie bude mať päťkrát viac vitrín ako predchádzajúce. Hlavná pointa stratégie je, že vždy počet vitrín násobíme tým istým číslom.

Poďme sa pozrieť, koľko Samko zaplatí pri tejto stratégií, ak je všetkých kuriozít sveta \(100\). Zase si úlohu rozdelíme na tri časti. Za všetky kuriozity sveta zaplatí \(100\) peňazí. Múzeá teraz bude kupovať s \(1, 2, 4, \ldots, 128\) vitrínami – \(128\) lebo je to prvá mocnina dvojky, ktorá je aspoň \(100\), čiže nám stačí na uskladnenie všetkých kuriozít. Takže za kupovanie múzeí tentokrát zaplatí \(1 + 2 + 4 + \cdots + 128 = 255\) peňazí. Za presun zaplatí \(1 + 2 + 4 + \cdots + 64\) peňazí, dokopy \(127\) peňazí. Za všetko dokopy zaplatí \(100 + 255 + 127 = 482\).

Porovnajme si túto stratégiu s ostatnými. Pri stratégii z podúlohy a) si pamätáme, že zaplatil \(1100\) peňazí. Ak by sme použili stratégiu z podúlohy b), tak by Samko zaplatil \(100\) peňazí za kuriozity, \(1\,000\,000\) peňazí za múzeum a nič za presun, pretože všetky kuriozity sa mu zmestia hneď do prvého múzea – dokopy \(1\,000\,100\) peňazí. V porovnaní násobiacou stratégia minie menej peňazí ako zvyšné dve.

Ak je všetkých kuriozít sveta \(10\,000\,000\), tak za ne zaplatí \(10\,000\,000\) peňazí. Za kupovanie múzeí zaplatí \(1+2+4+\cdots+2^{24}\), pretože \(2^{24}\) je prvá mocnina dvojky, ktorá je aspoň taká veľká ako \(10\) miliónov. Toto je v súčte \(2^{25}-1 = 33\,554\,431\). Za presun zaplatí \(1+2+4+\cdots+2^{23}\), dokopy \(2^{24}-1 = 16\,777\,215\). Nakoniec za všetko spolu zaplatí \(10\,000\,000 + 33\,554\,431 + 16\,777\,215 = 60\,331\,646\).

Poďme si túto stratégiu znova porovnať so zvyšnými dvoma. Ak by sme použili stratégiu z podúlohy a), tak by za kuriozity zaplatil \(10\,000\,000\), za múzeá by zaplatil \(5\,000\,005\,000\,000\) peňazí a za presuny \(4\,999\,995\,000\,000\), čo je dokopy viac ako \(10^{13}\) peňazí. Pri stratégií z podúlohy b) už vieme, že zaplatí \(110\,000\,000\) peňazí. V porovnaní so zvyšnými dvoma zase minie násobiacou stratégia menej peňazí.

Prečo je táto stratégia výhodná pre akýkoľvek počet kuriozít? Hlavným dôvodom je to, že pri násobení vitrín máme zo začiatku múzeá s malými počtami vitrín, pre menšie čísla a postupne sa dostávame rýchlejšie na väčšie a väčšie počty vitrín pre veľké čísla. Toto nám veľmi dobre balansuje to, ako často potrebujeme kupovať nové múzeá a teda aj presúvanie kuriozít.

Sada úloh 2 – Odkladanie kuriozít

Samkovi je najjednoduchšie dávať kuriozity do vitrín v poradí, čiže od \(1\) po \(n\) – počet vitrín v múzeu.

Podúloha a)

Na prvú podúlohu nám stačí, aby si zapamätal jednu premennú, označme si ju \(k\) ako koniec. Táto premenná hovorí o tom, do ktorej vitríny pôjde nasledujúca kuriozita, čiže kde je koniec poukladaných kuriozít. Na začiatku bude rovná \(1\) a zakaždým, keď Samko získa novú kuriozitu, tak sa premenná \(k\) zvýši o \(1\). Takže Samko vždy bude vedieť číslo vitríny, do ktorej pridá novú kuriozitu.

Podúloha b)

Pri druhej podúlohe si bude Samko musieť pamätať ďalšiu premennú, ktorú si označme \(z\) ako začiatok. Bude symbolizovať číslo vitríny, v ktorej je momentálna najstaršia kuriozita, čiže začiatok poukladaných kuriozít. Keďže si Samko ukladá kuriozity od prvej vitríny, tak na začiatku bude \(z = 1\). Pridávanie kuriozít do múzea \(z\) nijak neovplyvní, keď však bude Samko chcieť odstrániť najstaršiu kuriozitu, tak odstráni tú, ktorá je vo vitríne s číslom \(z\). Po odstránení sa \(z\) zvýši o \(1\), pretože teraz je najstaršia kuriozita v nasledujúcej vitríne.

Podúloha c)

Samko teraz neovplyvňuje, kedy získa novú a kedy odstráni najstaršiu kuriozitu. Ako teda zistí, že má plné múzeum a musí si kúpiť nové? Najpriamočiarejšie riešenie je to, že premenná \(k\) bude popisovať číslo vitríny, ktorá v múzeu neexistuje – predchádzajúca kuriozita bola pridaná do poslednej vitríny a \(k\) nesie číslo nasledujúcej, ktoré ale presahuje počet vitrín. Problém je však ten, že v takomto prípade by mohol mať na začiatku múzea prázdne vitríny, a tak sa Samkovi neoplatí kúpiť si nové múzeum – to sa mu oplatí iba vtedy, ak je múzeum naozaj úplne plné. Teraz má dve možnosti:

• Posunúť všetky kuriozity tak, aby boli znova od prvej vitríny. Tento spôsob je ale veľmi neefektívny, lebo musí veľa presúvať.
• Nastaviť si \(k\) znova od \(1\) a pridávať nové kuriozity do vitrín na začiatku. Týmto nám vznikne “hadík”, ktorý si naháňa svoj chvost. Tento spôsob je výhodnejší, lebo nemusíme presúvať žiadne kuriozity.

Keďže chce byť čo najefektívnejší, tak použije druhú možnosť. Tu je ukážka, ako táto možnosť funguje v praxi:

Pri nej ale musí nájsť iný spôsob, akým zistí, či má plné múzeum. Aj tento spôsob je pomerne jednoduchý. Múzeum bude plné, keď najmladšia kuriozita “dobehne” najstaršiu, teda keď sa \(k = z\). V takom prípade by Samko chcel nasledujúcu kuriozitu pridať do vitríny s číslom \(k\), ale v nej sa už nachádza najstaršia kuriozita.

V prípade, keď si Samko musí kúpiť nové múzeum, postupuje rovnako ako v prvej sade – kúpi si múzeum s dvojnásobným počtom vitrín.

Čo sa teraz stane s kuriozitami, keď treba kúpiť nové múzeum? Tým, že aj tak sa všetky kuriozity idú presúvať, tak si ich do nového múzea môže usporiadať tak, aby mal najstaršiu kuriozitu v prvej vitríne až postupne po najmladšiu kuriozitu. Čiže \(z\) sa prepíše na \(1\) a \(k\) sa prepíše na počet kuriozít \(+ 1\), pretože \(k\) je číslo vitríny, do ktorej budeme pridávať novú kuriozitu.