2002 MO P-I-2

Petr Baudis
SEPTIMA, gymnazium Ad Fontes Jihlava

Asi to nepujde o moc lepe nez trochu brute force metodou - postupne si zacneme
zkouset vsechny moznosti rozmisteni knih v knihovne - pro dve knihy to budou
moznosti ctyri, pro ctyri moznosti jiz moznosti rozmisteni do policek bude
sestnact etc.. v zasade moznych kombinaci bude O(N^2).

Pri generovani kazde knihovny si take budeme udrzovat maximalni sirku policky,
po dokonceni knihovny pak tuto sirku ucinime sirkou cele knihovny; pokud soucet
vysek vsech policek (plus sirky policek samotnych etc) bude mensi nez 250cm,
zkontrolujeme si, jestli nahodou tato knihovna neni nejuzsi, kterou jsme zatim
vyrobili; pokud ano, predchozi nejuzsi knihovnu zahodime a misto ni si
pamatujeme tuto. Po vygenerovani vsech knihoven staci pro onu nejuzsi knihovnu
vygenerovat nejaky rozumny vystup popisujici rozmisteni knizek.

Algoritmus bude zjevne fungovat vzdy, pokud existuje nejaka moznost usporadani
knizek, protoze zkousi vsechno moznosti.

Protoze zkousime N^2 kombinaci, bude casova narocnost O(N^2); staci si vsak
pamatovat jenom jednu z nich, coz nam dava pametovou narocnost O(N).