Keď sa Lukášovi podarilo preložiť si hľadanie dievčaťa do jeho materinského jazyku - do Júlie, riešenie sa mu zdalo priamočiare. A tak si teda našiel Julku. Lukáš a Julka si radi po večeroch píšu správy a tieto správy zvyknú byť občasne aj dosť dlhé. Lukáš však býva aspoň za 7 horami a jedným morom od Julky, a v dnešnej dobe sú u mobilných operátorov poplatky za medzinárodné správy dosť veľké. Obaja sú však chudobní študenti a peniaze na slohovky im už dávno došli. Pomôžte Julke nájsť spôsob ako poslať Lukášovy dlhú slohovku tak, aby neskončila na mizine a Lukáš si vedel (ne)spokojne správu prečítať.

Úloha

a. Lukáš sa potkol a tak poslal Julke správu "AAAAAAAAAAAAUAAAAAAAAAAAAUUUAAAAAAAAAAAAAAAAAAAAAAAAUAAAAAAAAAAAAAA". Na túto správu potreboval 67 znakov. Julka sa zujíma, či to naozaj bolo potrebné. Ako by vedel Lukáš túto správu skrátiť, tak aby nestratil žiaden znak na žiadnej pozícii? Dá sa to aj na 18 znakov?

b. Povedzme, že Lukáš sa tento krát nepotkol ale periodicky padal po schodoch. Aby Julke sprostedkoval tento galimatiáš¹, poslal jej správu "AUAUAUAUAUAUAUAUAUAUAUAUAU..." (Jedno "AU" pre každý schod). Vedel by Lukáš aj túto správu skrátiť tak, ako v predošlej úlohe? Ako sa táto správa odlišuje od predošlej úlohy?

c. Julka pozná veľa romantických slov ako napríklad ŤUŤMÁK, LINUX², HALDA, VZDUCH, MOJKO, ŠLAMASTIKA, a posiela ich vo svojích správach Lukášovi veľmi často. Napríklad Jukina správa môže vyzerať takto: AhojDvaŤUŤMÁKtrLINUXHALDAktoakMOJKOMOJKOŤUŤMÁKkdeVZDUCHHALDAvelkaŠLAMASTIKA. Každý deň používa iné slová a Lukáš, ako muž, nevie aké to sú. Správy, kde sa tieto slová vyskytujú často by Lukáš rád zapísal na čo najmenej znakov. Ako by vedel Lukáš túto správu zapísať čo najkratšie tak, aby sa nestratil ani jeden znak? Skús nájsť taký zápis, v ktorom čo najviac využije už napísaný text a čo najmenej bude písať znova.

d. Stručne popíš algoritmus, ktorým by si skracoval podobné reťazce.

e. Lukaš už odhalil Julkine ľúbostné slová, a tak si ich zapísal do slovníku³.

• kucharkaKSP
• lukosprava
• myxa
• kucapaca
• luk
• myxophyta
• kucho
• lukostrelba
• lukas
• kucharka
• luka
• myxopod
• kuchar

Chcel by ale zmenšiť počet znakov v každom slove, ktoré si viem ľubovolne usporiadať ako sa nám zíde. Ako by sme mali zoznam usporiadať tak, aby sme vedeli na každé slovo využiť čo najmenej znakov? Čo sa oplatí robiť so slovami s rovnakým začiatkom, vieme využiť podobný prístup ako v predošlej úlohe?

f. Jednoducho všeobnecne popíš algritmus, ktorým by si vedel slová zoradiť v predošlej úlohe. Možno ti pomôže zamyslieť sa nad výberom dátovej štruktúry.

g. Lukáš a Julka si vymenili svoje čísla. V rastúcej postupnosti veľkých čísel $k \leq a_1, a_2, a_3, \dots, a_n$ platí, že rozdiel dvoch po sebe následujúcich čísel $a_{i + 1} - a_i < k$. Chceli by sme ju skrátiť do postupnosti $n$ čísel, ktoré sú zaručene menšie ako $k$. Vieme si však k nim dovoliť pridať práve jedno číslo väčšie ako $k$. Ako to vieme docieliť?

h. Máme teraz zoznam $n \leq 10^k - 1$, kde $k \leq n$, veľkých po sebe idúcich čísel od $a, a+1, a+2, \dots , a+n-1 \leq 10^n - 1$. Nepoznáme $a,n,k$ a zoznamom vieme prejsť iba raz. Vieme ju zapísať pomocou dvoch čísel tak, aby každé z nich malo najviac $n$ číslic?