Po tejto strastiplnej skúsenosti so ženami sa Lukáš rozhodol, že mu predsa len je možno lepšie samému. Má však teraz ďalší problém - hrozne veľa voľného času. Vzišlo mu na um, že by mohol pomôcť vedúcim v sklade.

Sklad funguje tak, že je v ňom strašne veľa skriniek, očíslovaných 1, 2, 3 a tak ďalej. Tento sklad využíva veľa ľudí a každému v ňom patria niektoré skrinky, do ktorých si môže dávať veci. Do skladu nemôžeš len tak vojsť a napríklad ísť do cudzích skriniek, takže vždy, keď niečo potrebuješ, musíš si to vypýtať u skladníka. Keď si niečo od skladníka pýtaš, musíš za to aj zaplatiť, niekoľkými mincami. U skladníka si môžeš vypýtať tieto veci:

1. Prenajať si úsek skriniek. Povieš skladníkovi, koľko skriniek chceš, a on ti nájde v sklade súvislý úsek voľných skriniek, taký dlhý, ako potrebuješ. Skladník tieto skrinky vyhlási za tvoje, takže odteraz si do nich môžeš dávať veci. Potom ti skladník povie, na ktorom čísle sa tento tvoj úsek začína. Za toto celé mu musíš zaplatiť toľko mincí, koľko skriniek si prenajímaš.

   Takže napríklad ak si chceš prenajať 5 skriniek, môžeš zaplatiť 5 mincí a skladník ti povie napríklad, že tvoj úsek začína na čísle 74. To znamená, že skrinky 74, 75, 76, 77 a 78 sú teraz tvoje.

2. Dať niečo do prázdnej skrinky. Podáš skladníkovi vec, ktorú chceš do skladu uložiť, a povieš mu, do ktorej skrinky to chceš dať. Skladník skontroluje, či tá skrinka naozaj patrí tebe, a ak áno, tak tam tú tvoju vec uloží (inak ti povie, že skrinka nie je tvoja, a teda do nej nemôžeš dávať veci). Toto stojí jednu mincu.

3. Vybrať niečo zo skrinky. Povieš skladníkovi číslo skrinky, ktorá ti patrí (to skladník skontroluje), a skladník ti donesie to, čo v tej skrinke bolo uložené (alebo nič, ak bola prázdna). Toto tiež stojí jednu mincu.

Úlohy

Teraz by vedúci potrebovali pomôcť s tým, ako si to tam v sklade zorganizovať, aby sa vedeli dostať k tomu, čo potrebujú, a ideálne aby ich to nestálo príliš veľa mincí.

1. (ľahká, na rozohriatie) Vedúci poslali Krtka prenajať úsek 100 skriniek. To Krtko aj urobil a skladník mu povedal, kde začína jeho úsek. Teraz vedúci, ktorým sa nechce chodiť do skladu, obšas chcú od Krtka veci ako: dones mi to, čo je v skrinke číslo X (z tých našich 100), alebo daj niečo do skrinky číslo Y. Ako Krtko zistí, z ktorých skriniek (podľa číslovania v sklade) má tie veci brať, alebo do ktorých ich má dávať?

2. Vedúci už majú pekne dohodnuté, čo má byť na ktorom mieste v sklade, aby v tom bol poriadok, a aby vždy vedeli nájsť to, čo treba. Ale občas sa stane, že vedúci donesú nejaké veci zo sústredka a nemajú čas ich dávať na miesto, ale potrebujú sa ich len rýchlo zbaviť, a neskôr sa k tomu niekto vráti a uprace ich poriadne.

   Vymysleli si, ako by to chceli robiť. Predstavme si, že by neupratané veci dávali na kopu nad seba. Vždy, keď niekto príde s neupratanou vecou, tak ju dá na vrch kopy, a keď niekto príde upratovať, tak zoberie to, čo je práve na vrchu kopy, a uprace to.

   Napríklad sa môže stať, že je na začiatku všetko upratané, a potom príde Julka a dá na kopu laná, a po nej príde Lukáš a dá na kopu reflexné vesty, takže tie sú teraz na vrchu. Potom príde Krtko upratovať, tak zoberie z vrchu reflexné vesty a odloží ich na miesto. Na laná už ale nemá čas, tak ostanú na vrchu tie. Potom príde Gregor a dá na vrch šatky. Keď po ňom príde upratovať Kucho, tak najprv zoberie šatky, ktoré boli na vrchu, a uprace tie, a potom uprace laná, ktoré boli pod nimi.

   Lenže v sklade nie je možnosť mať veci na kope, iba v jednotlivých skrinkách. Ako teda vedia urobiť tento ich systém s kopou, pomocou skriniek? Môžu si na to prenajať niekoľko skriniek a potom dávať do nich a brať z nich veci. Môžeš predpokladať, že neuprataných vecí bude vždy najviac 100 (keby tam chceli dávať viac vecí, tak musia najprv upratať tie, ktoré tam už sú).

   Vedúci si môžu medzi sebou hovoriť niečo, čo potrebujú, ako napríklad na akom čísle začína ich prenajatý úsek. Aby si toho ale nemuseli hovoriť príliš veľa, chcú si takto hovoriť vždy najviac 5 čísel.

   Čo majú teda robiť? Popíš, čo majú spraviť na začiatku (napríklad prenajať si nejaké skrinky), a čo majú spraviť, keď chcú pridať nejakú neupratanú vec, alebo keď chcú zobrať vec z “vrchu kopy” a upratať ju.

3. Keď vedúci prišli na to, ako to robiť, tak im tento systém fungoval veľmi dobre, ale po čase narazili na jeden problém. Keďže ľudia vždy prinášali nové neupratané veci na kopu a upratovali tie veci na vrchu, tak sa občas stávalo, že k tomu, čo bolo na spodku kopy, sa veľmi dlho nikto nedostal, a potom to nevedeli nájsť. Rozhodli sa teda, že zmenia tento svoj systém.

   Namiesto toho, aby veci dávali “na kopu”, budú ich dávať “do fronty”. Teda môžeme si predstaviť, že máme rad vecí, ktoré čakajú na to, kým ich niekto uprace. Keď niekto prinesie novú vec, tak ju dá na koniec radu. Keď niekto príde upratovať, tak zoberie vec zo začiatku radu a uprace ju.

   Ako spravia takúto frontu v sklade? Môžeš predpokladať, že vedúci dokopy prinesú a potom upracú najviac 100 vecí. Inak to funguje rovnako ako v predošlej úlohe.

Vedúci nakoniec vymysleli, ako to urobiť, a potom už išlo všetko bez problémov. Fungovalo to však len nejaký čas. Vedúci tú svoju frontu totiž robili takým spôsobom, že sa stane nepoužiteľná po tom ako do nej 100krát niečo vložíme. Potom ju bolo treba úplne celú vyčistiť a začať od znovu.

Ako to majú robiť tak, aby fronta mohla fungovať donekonečna? Stále v nej môže naraz byť najviac 100 vecí, ale keď sa z nej veci upracú, malo by sa vždy dať do nej zase dávať ďalšie veci.

Ak takto funguje už tvoje riešenie predošlej úlohy, tak máš automaticky vyriešenú a nemusíš robiť nič. Ak má ale tvoje riešenie podobný problém ako to od vedúcich, ako by sa to dalo opraviť?

5. Zbierka materiálu na sústredká sa stále rozrastá: napríklad Jožko naposledy vytlačil kopu figúriek na plánikovku. Vedúci teda majú v sklade špeciálne miesto na nové, ešte nezaradené veci. Doteraz to robili tak, že na to mali prenajatý úsek, a keď sa im minulo miesto a potrebovali tam dať ďalšiu vec, tak prenajali nový, o 1 dlhší úsek, a všetko presunuli tam (nedá sa iba predĺžiť už prenajatý úsek, lebo je dosť možné, že hneď za ním už má prenajatú skrinku niekto iný).

   Toto ale začalo byť po čase dosť drahé: keď vedúci postupne doniesli 20 nových vecí, tak na prenajímanie úsekov použili postupne 1 + 2 + … + 10 = 190 mincí. Chceli by trochu viac šetriť. Skús vymyslieť, ako si majú tieto veci ukladať, aby potom, čo donesú prvých $N$ vecí, zaplatili za prenájmy najviac $3 \cdot N$ vecí.

   Teda napríklad ich pôvodný postup zo začiatku funguje, lebo pre 1 vec zaplatia 1 mincu, pre 2 veci 1+2=3 mince, pre 3 veci 1+2+3=6 mincí, pre 4 veci 10 mincí, pre 5 vecí 15 mincí, ale pre 6 vecí až 21 mincí, čo už je viac ako tých povolených 18. Prenajať si rovno na začiatku veľmi dlhý úsek by dlhodobo pomohlo, ale stojí to príliš veľa hneď na začiatku.