2. Prechádzka dobre uzátvorkovanými jaskyňami

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na

Úloha

Timka sa nedávno hrala svoju obľúbenú hru: Legend of Zelda. So svojou postavičkou sa pohybovala v podzemných jaskyniach (dungeonoch), zabíjala príšerky, zbierala mince a kľúče a pomocou kľúčov otvárala dvere do ďalších častí jaskyne.

V jednej chvíli sa ocitla na začiatku dlhočizného radu jaskyní. V každej z nich bol buď kľúč, ktorý mohla zobrať, alebo zamknuté dvere, ktoré bolo treba otvoriť na to, aby mohla pokračovať do nasledujúcej jaskyne. Kľúče, ktoré sa v tejto jaskyni nachádzali boli univerzálne, ale iba na jedno použitie. Každý kľúč teda vedel otvoriť ľubovoľné z dverí, mohol sa však použiť iba raz, po otvorení dverí zmizol. Aby to ale nebolo ťažké, Timka mohla niesť naraz ľubovoľne veľa kľúčov.

1. (3 body) Timka si na internete našla obrázok toho, ako vyzeral tento rad jaskýň – kde sa nachádzali kľúče a kde dvere. Zaujímalo by ju, či vie prejsť cez všetky tieto jaskyne, alebo je v hre naopak nejaká chyba a na koniec sa dostať nedá.

   Popíšte postup fungujúci pre ľubovoľne vyzerajúci rad jaskýň, ktorý Timke pomôže zistiť, či vie prejsť cez všetky z nich. Dajte si pozor, aby tento postup skutočne fungoval pri ľubovoľnom počte jaskýň a ľubovoľnom rozmiestnení kľúčov a dverí. Takisto napíšte, prečo je váš postup správny.

Na prvom obrázku sú jaskyne, cez ktoré Timka vie prejsť. Napríklad tak, že prvý kľúč nechá tak, zoberie až ten druhý, ten použije na otvorenie dverí v tretej jaskyni a následne už len bude zbierať kľúče a otvárať dvere. Mohla dokonca na začiatku zobrať aj ten prvý kľúč, aj keď by jej na nič nebol.

Jaskyňami na druhom obrázku Timka prejsť nevie. Nech spraví čokoľvek, ostane stáť pred druhými dverami bez kľúča.

2. (2 body) V ďalšej úrovni hry čakal na Timku ďalší rad jaskýň, situácia však bola o niečo komplikovanejšia. Dvere aj kľúče mohli mať dve farby – modrú a červenú, pričom modrý kľúč otváral iba modré dvere a červený kľúč iba čerevené. Timka teraz stojí pred tou istou otázkou. Dokáže prejsť cez všetky jaskyne?

   Popíšte postup, ktorý Timke povie, či cez zadanú postupnosť jaskýň vie alebo nevie prejsť. V tomto prípade však už musíte počítať s dvoma typmi kľúčov a dverí. Odôvodnite správnosť vášho postupu.

Obrázok vyššie ukazuje, ako by mohla vyzerať takáto sústava jaskýň. Je jasné, že v tomto prípade by sa Timke podarilo úspešne prísť až do konca.

3. (3 body) Na ďalší deň v škole riešili problém dobrého uzátvorkovania. Úloha znie tak, že máme zadaný výraz, napríklad \(((3 + 1) \cdot (7 - 3))\) a máme rozhodnúť, či je dobre uzátvorkovaný, teda či sa nám nejaká zátvorka nestratila, alebo nie je navyše. Napríklad vo výraze \((7 + (3 \cdot 4)\) nám chýba jedna ), aj keď nevieme na ktorom miesta¹.

   Aby sme sa zbytočne netrápili s číslami, uzátvorkovaný výraz si môžeme predstavovať iba ako postupnosť zátvoriek, teda prvý výraz by vyzeral (()()) a druhý ((). Pri zostavovaní dobre uzátvorkovaných výrazov sa riadime troma pravidlami:

   • () je dobre uzátvorkovaný výraz
   • ak je \(x\) dobre uzátvorkovaný výraz, tak aj (\(x\)) je dobre uzátvorkovaný – toto je úplne klasické uzátvorkovanie, napríklad \(4 \cdot (3 + 2)\) vieme uzátvorkovať na \((4 \cdot (3 + 2))\), ignorujúc čísla a znamienka, z () sme dostali (()).
   • ak sú \(x\) a \(y\) dobre uzátvorkované výrazy, tak aj \(xy\) je dobre uzátvorkovaný výraz – dva dobre uzátvorkovné výrazy vieme priložiť k sebe, napríklad ak máme \((4 + 2)\) a \((3 \cdot (2 - 1))\), tak vieme spraviť \((4 + 2) - (3 \cdot (2 - 1))\). Z () a (()) sme dostali ()(()).

   Keď sa Timka pozerala na tieto výrazy zátvoriek, veľmi jej to pripomínalo jej včerajšiu hru. Stačilo, keď si znak ( predstavila ako kľúč a znak ) ako dvere. A skutočne, tieto dva problémy boli rovnaké. Ak chcela zistiť, či je výraz dobre uzátvorkovaný, stačilo jej zistiť, či by prešla danou sústavou jaskýň.

   Teda skoro… Riešenie podúlohy a) malo predsa len jeden skutočne drobný nedostatok. Aký?

   Pomôžte Timke nájsť taký rad jaskýň obsahujúcich kľúče a dvere jednej (čiernej) farby, že nimi všetkými dokáže prejsť, ale ak zmeníme každý kľúč na ( a každé dvere na ), nedostaneme korektne uzátvorkovaný výraz. Upravte riešenie podúlohy a) tak, aby skutočne rozpoznávalo iba dobre uzátvorkované výrazy.

4. (3 body) Timka začala rozmýšľať nad tým, čo by sa stalo, keby jej výrazy mohli obsahovať dva typy zátvoriek – ( ku ktorej patrí ) a [ ku ktorej patrí ]. V jej hre s jaskyňami by zátvorky ( a ) boli modré kľúče a dvere a zátvorky [ a ] červené kľúče a dvere. Veľmi rýchlo však zistila, že jej riešenie podúlohy b) sa na tento problém použiť nedá.

   Nájdite takú postupnosť jaskýň obsahujúcu kľúče a dvere dvoch farieb, že keď zmeníme všetky červené kľuče na (, modré kľúče na [, červené dvere na ) a modré dvere na ], nedostaneme dobre uzátvorkovaný výraz.

   Tvorba dobre uzátvorkovaného výrazu pre dva typy zátvoriek sa riadi nasledujúcimi pravidlami:

   • () a [] sú dobre uzátvorkované výrazy
   • ak je \(x\) dobre uzátvorkovaný výraz, tak (\(x\)) a [\(x\)] sú dobre uzátvorkované výrazy
   • ak sú \(x\) a \(y\) dobre uzátvorkované výrazy, tak aj \(xy\) je dobre uzátvorkovaný výraz

5. (4 body) Popíšte postup, ktorý Timke povie, či je výraz pozostávajúci z dvoch typov zátvoriek (guľatých a hranatých) dobre uzátvorkovaný. Odôvodnite, prečo je váš postup správny.

   Dobre uzátvorkované výrazy sú napríklad ([])([[]]()) alebo [([()])], zle uzátvorkované sú ]([])(()) alebo ([()(][]).