Čtvrtá série osmého ročníku KSP

Zadání úloh

8-4-1 Cesta tam a zase zpátky (13 bodů)

Bylo jednou jedno království, ve kterém ke značné nelibosti místní fauny i flory začala jezdit auta. Jak již tomu bývá, auta jezdí po silnicích, které vedou mezi městy. Všechny silnice v říši jsou však jednosměrné (což neznamená, že z jednoho města do druhého nemůže vést jedna jednosměrka tam a druhá zpátky). Časem ale lidé zjistili, že se v některých oblastech začínají hromadit auta, neboť je možné, aby se z jednoho města dostali do druhého a zpátky se už nemohli vrátit ani oklikou.

Plynula léta, starého krále vystřídal na trůně jeho druhorozený syn (ten starší si totiž jednoho dne vyjel na obhlídku říše a nikdy se již nevrátil) a rozhodl se dostavět silniční síť tak, aby vedla cesta mezi libovolnými dvěma městy. Svému rádci pro dopravu zadal úkol, aby na příští zasedání královské rady připravil seznam silnic, jež je nutné dostavět, aby se dalo dostat (byť oklikou) z každého města do každého. Rádce se navíc rozhodl, že na krále udělá dobrý dojem tím, že připraví nejkratší možný seznam (tedy s co nejmenším počtem silnic, i když možná budou dost dlouhé) a po krátkém uvažování dospěl k názoru, že je to problém pro počítač, a najal vás, abyste za drobný bakšiš vytvořili program, který pro zadaný počet měst, počet dosud existujících silnic a jejich seznam nalezne alespoň jedno minimální řešení.

Příklad 1: 5 měst, dosud 3 silnice: 1→2, 2→3, 3→4. Odpověď: je třeba ještě vybudovat 4→5 a 5→1.

Příklad 2: 3 města, dosud 4 silnice: 1→2, 2→3, 3→2, 2→1. Odpověď: Silniční síť je vyhovující.

Řešení

8-4-2 Ďábelské mocniny (10 bodů)

Královský matematický ústav pořádá soutěž o nejlepšího matematika v říši. Všichni soutěžící dostanou zadáno spočíst danou poměrně vysokou mocninu nějakého velkého čísla a mají na to k dispozici mechanický kalkulátor nevalné kvality schopný za poměrně dlouhý čas vynásobit dvě zadaná čísla a k tomu také tužku a papír na poznámky (čísla jsou ovšem natolik dlouhá, že byť sečíst je ručně dá příliš mnoho práce).

Vy byste se též rádi soutěže zúčastnili – zkuste tedy vymyslet algoritmus, který pro daná přirozená čísla a a b nalezne postup, jak spočíst ab nejmenším možným počtem násobení.

Příklad: V prvním ročníku soutěže (tomu již jest drahně let) bylo zadáno 13376. Výherce si nejprve spočetl 13372 = 1337 ·1337 = 1787569 a poté 13376 = 13372 ·13372 ·13372 = 5712003219749941009.

Řešení

8-4-3 Top secret (11 bodů)

Královští vyzvědači zachytili tajnou depeši vyslance znepřátelené země. Aby mohli armádní experti na kryptoanalýzu tuto depeši rozluštit, potřebují pro dané číslo n zjistit jeho rozklad na součin dvou jiných čísel a,b>1. Poté, co jste se stali slavnými vyřešením dopravních problémů království, najali vás, abyste jim dodali program na řešení takovýchto problémů. Z dobře informovaných kruhů je známo, že číslo n je součin dvou prvočísel.

Ve svých řešeních můžete předpokládat, že se všechna čísla vejdou do 32-bitového celočíselného typu (long int v C, longint v Pascalu apod.). Algoritmus ale koncipujte tak, aby byl schopen zpracovávat co možná největší čísla n.

Řešení

8-4-4 Penězokazi (10 bodů)

Vrchní bankéř královské banky pojal podezření, že v království začínají řádit penězokazi a chce si ověřit, zda je oprávněné. Pokusil se shromáždit co nejvíce bankovek z jedné podezřelé série (v každé sérii je 100000 bankovek číslovaných od nuly do 99999) a rád by zjistil, zda některé dvě z nich mají stejné číslo. Činiti tak ručně by byla práce na mnoho dní, takže si chce zjednodušit práci pomocí počítače. Jenže bankovní počítač je poněkud staršího data výroby – má pouze 32KB programové paměti a 4KB datové paměti, zato však dostatek volného místa na disku.

Na vás je napsat program, který pro daných N čísel v rozsahu 0 až 99999 při splnění uvedených podmínek zjistí, zda se tam nějaké vyskytuje vícekrát. Rozhodující je rychlost programu – přístup na disk je nesrovnatelně pomalejší než přístup do paměti.

Řešení

8-4-5 (Ne)konečné automaty (15 bodů)

Náš seriál úloh o konečných automatech pokračuje…

a) Jsou dány jazyky

Sestrojte konečný automat přijímající jazyk L3.

b) Cenzorní úřad našeho království, jak se ostatně dalo předpokládat, pozorně sleduje i úlohy KSP a uvědomil si, že by se mu hodil inteligenční potenciál řešitelů k tomu, aby mohli lépe a radostněji cenzorovat novinové články. V první fázi by ocenili, kdyby byli rychle schopni zjistit, zda se v textu vyskytuje příslušné nevhodné či hanlivé slovo. Zakoupili totiž superrychlý interpreter konečných automatů, do nějž vloží dodaný text a příslušný konečný automat a on jim řekne, zda automat text přijme (což je pro autora špatné, neboť automat detekoval nepřípustné slovo), a tak jim stačí sestrojit pro každé nevhodné slovo konečný automat testující, zda se v textu toto slovo vyskytuje.

Jenže dlouhá léta vývoje obohatila národní jazyk království o neuvěřitelné množství nevhodných slov (za slovo se v tomto případě dokonce považuje i spojení více "klasických" slov pomocí mezer a interpunčních znamének) a kromě toho se jazyk vyvíjí, čili nevhodná slova přibývají, jména vladařů se mění (takže místo "Xaver je osel" se časem stane nevhodným "Rudpert je osel"), pročež potřebují práci zautomatizovat a navrhnout algoritmus, který pro dané slovo vygeneruje příslušný konečný automat, jenž přijímá právě texty toto slovo obsahující.

Běžné novinové články obsahují malá a velká písmena, mezery, čárky, tečky, vykřičníky a otazníky – konečný automat by tedy měl být definován nad touto abecedou. Pokuste se zvolit nějakou rozumnou formu výpisu definice automatu.

Poznámka: V terminologii konečných automatů je "slovo" vlastně celý námi zpracovávaný text, zatímco "podslovo" je hledané slovo v textu. Tudíž hledaný automat přijímá ta slova, která obsahují zadané podslovo.

Příklad: Pro slovo "baba" nám program nageneruje v KSP již zprofanovaný automat (přijme nejen větu "Královna je baba.", ale i větu "Dejte si pozor, lupič Řimbaba utekl z šatlavy!").

Řešení