Koniec kola: 5. august 2019 23:59
20 days
Počet bodov:
Popis:  15b

Ďaleko na severe, hlboko v Británii, v obrovskej knižnici ukrytej v útrobách podzemnej kamennej jaskyne už celé stáročia pracuje čarodejník Merlin. Merlin má na starosti veľké množstvo písomností z čarodejníckej literatúry, ktorá je pre ostatných čarodejníkov veľmi dôležitá.

Títo čarodejníci za ním najčastejšie chodia s troma typmi dotazov:

  • Sú tieto dve kúzla vo Veľkom zvitku rovnaké?
  • Nachádza sa v tejto knihe tento reťazec písmen?
  • Koľko many potrebujem na použitie tohto kúzla?

Merlin potrebuje čo najrýchlejšie odpovedať na tieto otázky, aby sa mohol venovať aj iným prospešným činnostiam.

Úloha

Merlin nevie veľmi rýchlo pracovať s textom a písmenami. Keď chce napríklad porovnať, či sú dva reťazce písmen rovnaké, postupne prechádza oba reťazce znak po znaku, až kým nenájde miesto, v ktorom sa líšia, alebo nepríde na koniec reťazcov. Ak napríklad porovnáva, či sú “abrakadabra” a “abrakazebra” rovnaké, porovnáva postupne “a”=“a”, “b”=“b”, “r”=“r”, “a”=“a”, a tak ďalej. Postupne overí, že prvých šesť znakov je rovnakých a potom na siedmom znaku má jeden reťazec písmeno “d” a druhý “z”. Tieto reťazce teda nie sú také isté.

Overiť, že “athraighanboscaadhmaidseoinachloch” je to isté ako “athraighanboscaadhmaidseoinachloch” mu trvá 34 krokov. Pokiaľ by sa nejaké reťazce zhodovali na prvých dvetisíc znakoch a odlišovali sa na dvetisíc prvom, trvalo by mu zistiť, že sú rôzne, 2001 krokov. To je príliš dlho.

Podobne overiť, či sa nejaký reťazec nachádza v nejakej knihe je ťažké. Napríklad aby zistil, či sa \(R =\)ababababac” nachádza v \(K =\)abababababababababab”, postupoval Merlin tak, že postupne overoval: Je prvých 10 znakov K rovnakých ako R? Sú znaky 2 až 11 v K rovnaké ako R? Sú znaky 3 až 12 v K rovnaké ako R? Sú znaky 4 až 13 v K rovnaké ako R? Sú znaky 5 až 14 v K rovnaké ako R? A tak ďalej až po: Sú znaky 11 až 20 v K rovnaké ako R?

Na to potreboval \(10 + 1 + 10 + 1 + 10 + 1 + 10 + 1 + 10 + 1 = 55\)-krát porovnať nejaké dva znaky (10 porovnaní v prípade, že dané písmená v \(K\) tvorili reťazec "ababababa" a až potom prišlo na nezhodu s písmenom "c", 1 porovnanie v prípade, že postupnosť v \(K\) začínala písmenom "b" a teda chybu objavil hneď pri prvom porovnaní). Overiť, či sa 1000 znakový reťazec nachádza v milión znakov dlhej knihe môže trvať skoro až miliardu krokov. A to je dosť veľa.

 

Na druhú stranu, ako správny čarodejník, Merlin dokáže rýchlo pracovať s číslami. Sčítať, vynásobiť či porovnať dve čísla mu trvá jeden krok bez ohľadu na to, aké sú čísla veľké. Podobne jednoduché operácie s jedným alebo dvoma číslami, vie tiež robiť takto rýchlo, ale keď je čísel viac, nevie to spraviť naraz. Sčítať \(n\) čísel by mu stále trvalo \(n-1\) krokov.

Často, keď Merlin pracuje s reťazcami, prevedie si ich na zoznam čísel. Písmena abecedy si očísluje od a=1 až po z=26 a potom reťazec písmen je zoznam k nim prislúchajúcich čísel. Napríklad “abrakadabra” = 1, 2, 18, 1 11, 1, 4, 1, 2, 18, 1.

Nasledovné pojmy súčet a magické číslo budeme používať v podúlohách, tak si ich teraz popíšme.

Súčet nejakého reťazca je súčet jeho písmen prevedených na čísla. Napríklad súčet “abrakadabra”, je \(S\)(abrakadabra) = \(1+2+18+1+11+1+4+1+2+18+1 = 60\).

Magickú hodnotu nejakého reťazca vypočítame nasledovne: Opäť písmenám priradíme čísla a=1z=26, ale tentokrát tieto písmená pred sčítaním ešte niečim vynásobíme. Posledný znak vynásobíme jednotkou, predposledný číslom 47, predpredposledný číslom 47 krát 47. \(i\)-ty znak od konca (začínajúc od \(i=0\)) \(i\) krát vynásobíme číslom 47.

Magická hodnota reťazca “zebra” je \(M\)(zebra) \(= 47^4\cdot 26 + 47^3\cdot 5 + 47^2\cdot 2 + 47\cdot 18 + 1\cdot 1 =\) \(4879681\cdot 26 + 103823\cdot 5 + 2209\cdot 2 + 47\cdot 18 + 1 =\) \(126871706 + 519115 + 4418 + 846 + 1 =\) \(127396086\) (Zápis \(a^k\) voláme umocňovanie a je to zápis pre vynásobenie čísla \(a\) \(k\)-krát. Napríklad \(47^4 = 47\cdot 47\cdot 47\cdot 47 = 4879681\))

Podobne magická hodnota reťazca “abrakadabra” je \(M\)(abrakadabra) \(= 55266621785409182\).

Vypočítať súčet či magické číslo nejakého reťazca dlhého \(\ell\) zaberie Merlinovi rádovo \(\ell\) krokov.

Podúloha a – úvod

V Merlinovom Veľkom zvitku sú postupne napísané všakovaké kúzla, v poradí v akom ich jeho predkovia objavili. Každé kúzlo je reťazec malých písmen anglickej abecedy. Mohlo sa stať, že nejaké kúzlo bolo objavené viackrát, a tak sa môže vo zvitku nachádzať rovnaké kúzlo opakovane. Ostatní čarodejníci pravidelne Merlina navštevujú a pýtajú sa ho otázky tvaru: “Je \(i\)-te kúzlo a \(j\)-te kúzlo vo Veľkom zvitku rovnaké?”

Merlin tiež vlastní Malý zvitok, ktorý si už dávnejšie vyrobil. Na \(i\)-tom riadku tohto zvitku je napísaný súčet \(i\)-teho kúzla a tiež jeho magická hodnota, ktoré spočítal postupom uvedeným vyššie.

Merlin teraz rozmýšľa, či by nedokázal použiť Malý zvitok na to,
aby dokázal by na otázky čarodejníkom rýchlo a okamžite, bez toho aby kúzla porovnával pracne, znak po znaku.

Podúloha a – (4 body)

Nájdite dve rôzne kúzla, ktoré majú rovnaký súčet, alebo stručne ukážte, prečo také kúzla neexistujú.

Nájdite dve rôzne kúzla, ktoré majú rovnakú magickú hodnotu, alebo stručne ukážte, prečo také neexistujú.

Stručne popíšte postup, ako Merlin môže odpovedať na otázky ostatných čarodejníkov, len pomocou Malého zvitku. Napríklad, čo s čím má Merlin porovnať a ako má vyhodnotiť výsledok, ak chce zistiť, či sú \(i\)-te a \(j\)-te kúzlo vo Veľkom zvitku rovnaké.

Podúlohy b a c. – úvod

Niektorí čarodejníci nevedia čítať. A tak chodia za Merlinom, donesú mu knihu dlhú \(k\) znakov a spýtajú sa, či sa v knihe nachádza nejaký konkrétny reťazec dlhý \(r\) znakov.

Napríklad “braka”, “dabra” aj “a” sa nachádzajú v “abrakadabra”, ale “zebra” ani “aaa” sa tam nenachádzajú.

Podúloha b (3 body)

Kráľ Pendragon mal rád čísla, pravidelnosť a rád písal knihy. Všetky jeho knihy majú presne milión znakov (malých písmen anglickej abecedy) a majú zaujímavú vlastnosť: Každý úsek 1000 znakov v nej má iný súčet.

Navrhnite postup, ako efektívne zistiť, či sa zadaný 1000 znakový reťazec nachádza v danej knihe napísanej kráľom Pendragonom.

Keď hovoríme “efektívne” máme tým namysli, že tento postup netrvá príliš dlho. Skúste nájsť postup, ktorý potrebuje niekoľko miliónov krokov, prípadne zopár desiatok miliónov krokov, nie však miliardu.
Bežné matematické operácie, ako previesť písmeno na číslo, sčítať dve čísla, porovnať dve čísla, vynásobiť dve čísla trvajú jeden krok. Avšak už sčítať \(n\) čísel, alebo pozrieť sa na \(n\) hodnôt trvá \(n\) krokov.

Podúloha c (3 body)

Navrhnite spôsob, ako efektívne zistiť, či sa zadaný reťazec \(R\) dĺžky \(r\) nachádza v zadanom reťazci \(K\) dĺžky \(k\).

Poznámky: O reťazci \(K\) už nemáte žiadne záruky, ako v predošlej podúlohe. Možno sa vám bude lepšie spisovať riešenie, ak budete používať označenie \(K_i\) resp. \(K[i]\) pre \(i\)-ty znak knihy a \(R_j\) resp. \(R[j]\) pre \(j\)-ty znak hľadaného reťazca. Rada: zamyslite sa, či sa dajú použiť magické čísla popísané vyššie v zadaní.

Podúloha d. (5 bodov)

Každé kúzlo potrebuje na vyčarovanie toľko many, koľko jeho začiatkov (prvých niekoľko písmen) je zároveň aj jeho koncom (posledných niekoľko písmen). Napríklad kúzlo “abrakadabra” spotrebuje 3 many, lebo “a”, “abra” a “abrakadabra” sú všetko začiatky, ktoré sú zároveň aj konce. Kúzlo “aaaaa” spotrebuje 5 many a “ttottogttottogttottogtt” tiež 5 many (začiatky a zároveň konce sú “t”, “tt”, “ttottogtt”, “ttottogttottogtt” a celé kúzlo). Kúzlo “abracaz” potrebuje len jednu manu, lebo žiaden začiatok okrem celého kúzla nie je aj koncom.

Navrhnite postup, ktorý pre dané kúzlo čo najrýchlejšie vypočíta, koľko many potrebujeme na jeho vyčarovanie. Váš postup by mal použiť rádovo toľko krokov, aká je dĺžka kúzla.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.