1. Praktiky väznice Guantanámo

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Máriovi Lipovskému na

Dvaja vedúci Prasku nedávno cestovali po svete a rozhodli sa, že navštívia väznicu Guantanámo. Šikovní väzni si ich hneď všimli, zobrali im oblečenie a vymenili sa s nimi. Pre stráže všetci vyzerajú rovnako a nikto našim vedúcim neuverí, že tam nepatria. To by predsa mohol povedať každý.

Vedúci si teda musia začať zvykať na väzenský život. Na dennom programe majú skoré budíčky, malé porcie jedla, studené sprchy, žiadny internet a guantanámske šarády. Veľmi sa im to tam nepáči, a tak sa rozhodli utiecť. Nebude to však také ľahké. Skúšali kopať tunel, preliezť plot aj podplatiť stráže, ale nič z toho sa im nepodarilo. Teraz majú nový nápad – utiecť počas obeda. Chcú pri tom využiť fakt, že na obed ich volajú v poradí, v akom sú napísaní vo veľkom zozname väzňov.

Každý väzeň dostal nové meno. Toto meno je zložené z prvých štyroch písmen abecedy a každé písmeno je použité práve raz. Všetky mená sú tiež rovnako dlhé. Takže mená, aké mohli dostať sú napríklad “ABCD” alebo “DCAB”, ale nemohli dostať mená “DAAB”, ani “FGAB”, ani “ABC”. Tieto mená sú zapísané v zozname väzňov v abecednom poradí (presne tak, ako by boli napísané v slovníku). Vedúci potrebujú zistiť viacero vecí pred tým, ako môžu utiecť. Po tom, čo kopali tunel sú ale dosť unavení. Pomôžete im?

Úloha

Okrem samotných odpovedí k úlohám popíšte aj postup, ako ste sa k výsledkom dopracovali.

1. (2 body) Vedúcich by zaujímalo, koľké v poradí je v zozname väzňov napísané meno “DBAC”.

2. (3 body) Vedúci sa boja, že ich presunú do najväčšej väznice na svete, kde používajú rovnaký systém mien, akurát každé meno má 15 písmen. Takže prvé v zozname je teraz meno “ABCDEFGHIJKLMNO”. Zistite, koľkým väzňom môže dať takáto väznica meno.

3. (1 bod) V Guantanáme nedávno prešli na 5-písmenové mená, lebo mali príliš veľa väzňov. Vedúci si všimli, že ich mená začínajú na písmeno D. ,,To je ale náhoda,’’ povedali si. Aby vedeli, aká veľká náhoda to naozaj je, máte im povedať, koľko väzňov dokopy môže mať meno začínajúce na D.

4. (1 bod) Pri úteku im bude pomáhať väzeň DABCE. Chcú vedieť, koľký v poradí je napísaný v zozname on.

5. (2 body) Počas obeda budú mať veľmi málo času na útek. DABCE bude utekať prvý a DEABC posledný. Spočítajte, koľko väzňov je medzi nimi v zozname.

6. (6 bodov) Útek sa nepodaril a Guantanámo sa rozhodlo zvýšiť bezpečnosť. Ako jedno z opatrení prešli na dlhšie mená a vedúcim by sa zišlo nájsť algoritmus, ktorý by im vedel povedať koľké v poradí je hocijaké meno zapísané v slovníku. Vymyslite a popíšte, ako funguje takýto algoritmus. Skúste aj dokázať, že správne určí poradie každého mena. Ukážte, ako by fungoval na konkrétnych menách “FACDEB”, “AEGFDBCH”, “DIECAHFGB” a “BHACDEFGJI”.

Algoritmus je postup jednoduchých krokov, pomocou ktorých vyriešime problém – zistíme poradie mena v zozname. Algoritmus musí tiež zistiť správne poradie pre ľubovoľné meno, ktoré spĺňa všetky podmienky zadania – každé písmeno len raz a meno obsahuje prvé písmena abecedy.

Dajte si pozor na to, že v zozname sú vždy napísané len rovnako dlhé mená – teda ak rátame poradie slova “ABCDEF”, tak bude prvé, lebo nie je žiadne slovo dĺžky 6, ktoré spĺňa podmienky a ktoré by v abecede ležalo pred “ABCDEF”.