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

Jedného dňa sa k Andejovi nasťahovala žaba. Všetko by bolo v poriadku, keby sa neusídlila priamo na Andrejovom notebooku. Našťastie si Andrej spomenul, že ako malý sa hrával s kockami. Teraz sa už s nimi síce nehráva, ale zato ich má plnú pivnicu. Rozhodol sa preto, že tam žabu zanesie a postaví jej tam dom. Čo dom, celé mesto! Len nech ho už nechá konečne na pokoji.

Také mesto z kociek sa skladá z viacerých budov poukladaných vedľa seba v obdĺžnikovej mriežke. Každá budova je tvorená niekoľkými na seba poukladanými kockami, tvorí teda vežu širokú a dlhú jednu kocku. A aby bolo mesto pekné, jednotlivé budovy spolu susedia celými hranami.

Na obrázku 1 si môžete pozrieť ako môžu vyzerať dve takéto mestá. A keďže iba z nákresu nemusí byť jasné, kde je ako vysoká budova, môžeme použiť alternatívny zápis, v ktorom do štvorčekovej siete na každé políčko zapíšeme výšku budovy, ktorá sa tam nachádza. Treba si však dať pozor na to, aby sme si označili orientáciu takéhoto nákresu.

Andrej však postavil mesto do rohu miestnosti. Žaba ho preto vidí iba spredu a sprava. A keďže kocky sú všetky rovnaké a precízne poukladané, budovy v jednom riadku alebo stĺpci sa jej zlievajú dokopy. Na obrázku 2 si môžete pozrieť, čo vlastne vidí pri pohľade na mesto. Zaujímavé je, že takýto pohľad by dostala pre obe mestá na obrázku 1.

Úloha

Žaba má strach z výšok. Hanbí sa to však povedať Andrejovi. Preto by chcela vedieť, či pre ňu mesto nie je privysoké. Zaujímalo by ju preto, aká je výška najvyššej budovy v meste, a koľko budov má takúto výšku. K dispozícii však má iba pohľad spredu a sprava. A v prípade, že počet najvyšších budov nie je jednoznačný, zistite, koľko najmenej a najviac ich tam môže byť.

1. (3 body) V tejto podúlohe máte na obrázku 3 zadané pohľady na dve konkrétne mestá. Pre obe tieto mestá zistite vyšku najvyššej budovy a počet takto vysokých budov. Do popisu okrem odpovedí napíšte aj zdôvodnenie, prečo je vaša odpoveď správna a postup, akým ste sa k nej dopracovali.

Napríklad z nákresov na obrázku 2 vieme určiť, že najvyššia budova v meste má výšku 4 a v celom meste je len jedna takáto budova.

1. (4 body) Žabu stále zaujíma výška najvyššej budovy a počet najvyšších budov. Chcela by to však vedieť povedať pre ľubovoľné mesto. Nájdite a popíšte postup, vďaka ktorému dokáže žaba z dvoch pohľadov na mesto – spredu a sprava – zistiť hľadané informácie.

Žaba je s mestom spokojná, rada by sa však vrátila späť do bažiny. Chcela by si v nej preto postaviť úplne rovnaké mesto. Samozrejme, z dvoch pohľadov nemusí byť úplne jasné, ako má také mesto vyzerať. Zaujímalo by ju preto, ako by ho mohla postaviť čo najveľkolepejšie, teda použitím najväčšieho možného počtu kociek. No a pre prípad, že by materiálu v bažine nebolo dosť, ako postaviť rovnako vyzerajúce mesto s najmenším počtom kociek.

Jej cieľom je teda postaviť mesto, ktoré z oboch pohľadov vyzerá rovnako ako to Andrejove, ale obsahuje najviac, poprípade najmenej, kociek. Ak by mala k dispozícii napríklad pohľady z obrázku 2, výsledné najväčšie a najmenšie mesto si môžete pozrieť na obrázku 1.

1. (3 body) Pre pohľady z obrázku 3 zistite, ako by vyzerali im zodpovedajúce mestá s najväčším a najmenším počtom kociek. Výsledok zapíšte vo forme štvorčekovej siete tak ako je to na obrázku 1. Okrem samotných mriežok (v tomto prípade by mali byť 4 – najväčšie a najmenšie pre obe mestá A a B) popíšte aj spôsob, akým ste sa k tomuto výsledku dostali a prečo je správny.

2. (5 bodov) Pomôžte žabe vymyslieť postup, vďaka ktorému pre ľubovoľný pohľad spredu a sprava určí, ako vyzerá im zodpovedajúce mesto s najväčším a najmenším počtom kociek. Váš postup musí fungovať pre ľubovoľné dva pohľady. Môžete predpokladať, že zadané pohľady naozaj zodpovedajú nejakému mestu.