KOMINÁR ročník 2000/2001

1.séria úloh

(termín odoslania riešení : 26.2.2001)

Bitland je krajina, o ktorej sa všeličo povráva, ale v encyklopédiach o ňom nenájdete zmienku. Žeby bol taký bezvýznamný ? Určite nie, ale všetci cestovatelia, ktorí sa odtiaľ vrátili, onemeli - my tvrdíme, že od úžasu. Veď posúďte sami.

- 1 -

Bitland je celý posiaty nádhernými vežovitými stavbami. Takéto stavby nikde na svete neuvidíte, snáď len šikmá veža v Pizze (aj tá sa staviteľom trochu vymkla z rúk) je zlomkom krásy, ktorú doďaleka vyžarujú bitlandské veže. Všetko to začalo raz dávno za vlády bitlandského kráľa Pentijaka I.. V krajine sa pretekali stavební umelci, kto viac očarí kráľa svojou stavbou. Nakoniec si priazeň kráľa získal Bitko Hanoj, so svojou trojpodlažnou vilou valcového vežovitého tvaru. Móda trojpodlažných víl podľa Hanojovho vzoru sa rýchlo rozšírila a nádherne vyzdobené vily sa stali ozdobou každého kúta ostrova. Bitkovia boli týmito stavbami natoľko posadnutí, že sa v tvare Hanojských veží začali vyrábať aj strúhadlá na ceruzky, aktovky, rôzne hračky, ale najväčšej obľube sa tešil hlavolam - Hanojská veža. Samotný hlavolam zvýrazňuje nielen krásu, ale aj potrebný dôvtip a vytrvalosť, bez ktorých sa stavba naozajstnej veže nemôže podariť. Skúste sa s takýmto hlavolamom popasovať aj vy.

Na začiatku máte tri plošiny - základne a na jednej z nich stojí Hanojská veža (môže byť postavená z mincí rôznej veľkosti). Vašou úlohou je prestavať túto vežu na inú z troch plošín tak, že

a, Naraz môžete presunúť na niektorú z plošín len jedno podlažie,

b, V žiadnom prípade nemôžete položiť väčšie podlažie na podlažie menšie

Na obrázku vidíte najrýchlejší postup prestavby trojpodlažnej Hanojskej veže. Vašou úlohou je napísať postup pre prestavbu šesťpodlažnej Hanojskej veže. Plný počet získajú tí z vás, ktorí dokážu napísať postup (algoritmus) pre n-podlažnú Hanojskú vežu, kde n je ľubovoľné vopred známe prirodzené číslo väčšie ako 3.

 

- 2 -

Kráľ Pentijak I. najradšej relaxoval s hlavolamom Hanojskej veže v jednej z dvoch rovnako veľkých štvorcových záhrad Z1 alebo Z2 svojho letného sídla. Samotná budova letného sídla A bola avantgardná hanojská veža v tvare štvorca so stranou 10m. Aj ostatné časti letného sídla - hlavné nádvorie N, športový areál S a jazierko J boli štvorcového tvaru a obklopovali sídlo tak, ako to znázorňuje obrázok. Vedeli by ste určiť, aký veľký bol celý areál kráľovho letného sídla a taktiež aké veľké boli jeho jednotlivé časti ? Svoj postup nezabudnite vysvetliť.

- 3 -

Bitko Hanoj si vďaka svojmu staviteľskému vynálezu dobre zarobil a celý život už nemusel nič robiť. To však pri jeho povahe bolo prakticky nemožné. Jediné, čo si naozaj neodoprel, bolo vysedávanie v bitlandskom archíve zaujímavých úloh a hlavolamov. Na vine bola jedna v hrošej koži viazaná stará bitlandská kniha SEZAM, OTVOR SA plná práve takýchto úloh. Že boli naozaj zaujímavé, posúďte sami. Tá dnešná je o poslednom dovolenkovom dobrodružstve dvoch vesmírnych prieskumníkov kapitána Gargantuu (Grg) a pilota Pantagruela (Pánt): "Žiaľ dni odpočinku a mimoriadnej dovolenky rýchlo utiekli, a bolo treba vrátiť sa do služby. Okrem zaplatenia účtu bolo treba aj vrátiť vypožičané rekreačné pomôcky. Grg s Pántom mali požičané 3 nafukovacie lehátka a 3 nafukovacie vznášadlá. V požičovni samozrejme pracoval robot, ktorý ale vzhľadom na zúriace leto dostal elektronický úpal, a obsluhoval veľmi zvláštnym spôsobom. Mohli ste mu vrátiť len jedno alebo dve lehátka, a jedno alebo dve vznášadlá. Ak ste mu vrátili jedno lehátko, hneď vám iné lehátko požičal. Keď ste mu vrátili vznášadlo, požičal vám dve iné vznášadlá. Ak ste mu vrátili dve vznášadlá, požičal vám jedno lehátko. Len keď ste mu vrátili dve lehátka, prebral ich a nič nové vám nevnútil. Samozrejme pri každej takejto operácii robot vypisoval kopu potvrdení, a bol po nej taký unavený, že na pol hodiny odišiel oddychovať. Pretože Grg s Pántom nechceli stráviť ďalší rok vracaním nafukovačiek, rozhodli sa najskôr premyslieť postup tak, aby robota navštívili čo najmenej krát." No čo poviete, úžasné však ? Napíšte nám, ako najrýchlejšie (na čo najmenší počet návštev) mohli Grg s Pántom vrátiť 3 lehátka a 3 vznášadlá pripečenému robotovi. Okrem výsledku nezabudnite napísať aj Váš postup !

- 4 -

Hanoj sa rozhodol skontaktovať s autorom tejto fantastickej zbierky úloh, pozrel si v knihe jeho meno, v telefónnom zozname našiel jeho číslo, ale ... nemal pero a papier a nechcel riskovať, že si číslo zle zapamätá, preto v ňom začal hľadať nejaké zákonitosti.

Už to mám - Druhá polovica čísla je štvornásobkom prvej.

A dve prostredné číslice sú rovnaké.

No a druhá číslica je dvojnásobkom prvej a to by mohlo stačiť.

Keď prišiel Hanoj domov, sadol si k telefónu a začal zo zapamätaných zákonitostí skladať potrebné telefónne číslo až sa mu tvár skrivila od zúfalstva. Nájdených zákonitostí bolo málo. Úporne sa snažil spomenúť na chýbajúce číslice, ale márne. Nakoniec si spomenul, že ho v knižnici napadla ešte nejaká zákonitosť, ale už si nebol istý, či tretia číslica má byť dvakrát väčšia ako druhá alebo o dva väčšia ako druhá. Ešte chvíľu si lámal hlavu, ale napokon zistil, že aj to mu stačí a výsledné číslo je už úplne jasné. Od radosti zdvihol telefónne slúchadlo a ... Vedeli by ste aj vy zistiť, aké číslo má autor knihy SEZAM, OTVOR SA, ak viete ešte, že všetky telefónne čísla na Bitlande sú šesťmiestne a nemôžu začínať nulou ? Svoje riešenie poriadne zdôvodnite.

- 5 -

A čo naši starí známi Bitko Kompík a jeho robot Karol ? (Kto ich nepozná alebo na nich zabudol, nech si pozrie úlohy minulých ročníkov, kde sa oboznámi s najdôležitejšími doposiaľ známymi schopnosťami robota). Spomenuli sme si na nich práve v čase najväčšieho frmolu. Pracujú deň-noc na plagátoch, vlajkách, vstupenkách a iných rekvizitách pre bitlandské olympijské hry. Najprv sa zdalo všetko jednoduché, stačilo mierne upraviť Karlovu schopnosť vytvárať mozaikove dlažby, pridať držiak na štetec a maliarsku čapicu a do elektroniky pridať funkciu

ZAMAĽUJ (Karol zamaľuje políčko, na ktorom stojí)

Kompík robota naprogramoval pre namaľovanie olympijských kruhov podľa priloženej predlohy

a od tej chvíle si Karol vychutnáva tisícky a milióny svojich maliarskych diel, až sa mu z toho krúti jeho kockatá hlava. Práce je však tak veľa, že Kompík má skôr kruhy pod očami. Musí totiž urobiť Karlovi dvojníkov, dokonca v rôznych veľkostiach (miniatúrneho pre kreslenie kruhov na vstupenky, či obra, ktorý to isté nakreslí na veľkoplošné plagáty, ...) a urobiť najúspornejší možný program (program obsahujúci najmenej príkazov), aby sa jeho zákazka zbytočne nepredražila. Dokážete mu s týmto programom pomôcť ?