Třetí série osmého ročníku KSP

Zadání úloh

8-3-1 Kouzelné zrcadlo (13 bodů)

Byla jednou jedna docela obyčejná královna, která vlastnila jedno ne zcela obyčejné zrcadlo a z poměrně nejasných pohnutek po něm stále žádala, aby jí ukázalo, kdo že je to na tom světě nejkrásnější, načež se divila, že se zrcadlo nechová tak, jak se od běžného zrcadla obvykle očekává. Jistě nemusíme pokračovat – tuto pohádku dozajista všichni dobře znáte.

Napište program, který se bude chovat přesně jako dotyčná královna a pro daný text na vstupu rozhodne, je-li to jeho vlastní zdrojový text (v takovém případě odpoví něco ve stylu "Tak přeci je to zrcadlo kouzelné!", v případě opačném pak "Xakru, zase to nefunguje!"). Program ovšem nesmí používat žádné soubory.

Řešení

8-3-2 Magické čtyřky (13 bodů)

X byl profesionální mág a současně matematik amatér. A nebo opačně – vyberte si. Vzhledem k tomu, že měl velice omezené možnosti, počítal pouze s malými celými čísly v rozsahu 0 až p-1 (za p si z nějakého rozmaru vybíral pouze prvočísla) a zavedl si s nimi následující operace:

a ⊕b = (a+b) mod p
a ⊖b = (a-b+p) mod p
a ⊗b = (a ·b) mod p
a ⊘b = (a ·bp-2) mod p

(vyzkoušejte si, že se tyto operace chovají podobně jako normální sčítání, odčítání, násobení a dělení celých čísel).

X navíc považoval číslo 4 za číslo magické (čtyři přeci jsou živly, světové strany, strany čtverce, rozměry časoprostoru a jiné důležité věci). Proto se rozhodl studovat, kolik čísel 4 spolu s popsanými celočíselnými operacemi stačí k zapsání každého čísla od 0 do p-1. Takovýto minimální počet čtyřek pro dané p nazval magickou konstantou svého číselného systému a ihned odvodil, že pro p=5 to je 3:

0=4⊖4,    1=4⊗4,    2=4⊕4⊕4,    3=4⊕4

Záhy však zjistil, že pro velké p je poměrně náročné hodnotu magické konstanty zjistit, a tak se obrací na Vás, abyste mu napsali program, který pro dané prvočíslo p>4 příslušnou hodnotu určí.

Řešení

8-3-3 Nešťastný pátek (10 bodů)

Říká se, že neštěstí nechodí po horách, ale … například po pátcích třináctého. Za rok obzvláště šťastný je dozajista možno považovat takový, v němž není ani jeden pátek třináctého, naopak za nad míru nešťastný pak ten, kde jsou takové tři nebo dokonce více. Napište program, který pro daný rok r>1582 zjistí, kolik je v něm zmíněných nešťastných pátků.

Pro ty z vás, kteří neznají přesná pravidla kalendáře, podotýkáme, že přestupné jsou roky dělitelné čtyřmi, pokud ovšem nejsou dělitelné stem. Jsou-li dělitelné stem, jsou přestupné jen tehdy, jsou-li navíc dělitelné čtyřmi sty.

Řešení

8-3-4 Základní kámen (10 bodů)

Vítejte ve světě matematické logiky. Všude okolo jsou logické výrazy, logické operace a logické proměnné. Pojďme si je nyní prohlédnout zblízka. Nejprve operace:

0 and 0 = 0
0 and 1 = 0
1 and 0 = 0
1 and 1 = 1
0 or 0 = 0
0 or 1 = 1
1 or 0 = 1
1 or 1 = 1
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
0 ⇒ 0 = 1
0 ⇒ 1 = 1
1 ⇒ 0 = 0
1 ⇒ 1 = 1
0 ≤ 0 = 1
0 ≤ 1 = 0
1 ≤ 0 = 1
1 ≤ 1 = 1
0 nand 0 = 1
0 nand 1 = 1
1 nand 0 = 1
1 nand 1 = 0
0 nor 0 = 1
0 nor 1 = 0
1 nor 0 = 0
1 nor 1 = 0
not 0 = 1
not 1 = 0

Pak jsou zde proměnné označované malými písmeny latinské abecedy (tedy a až z) a konečně výrazy složené z operací a proměnných podle následujících pravidel:

Operace nand a nor jsou ovšem něčím zvláštní – jsou to totiž základní kameny matematické logiky – pomocí každé z nich (a bez ostatních funkcí) je možno zapsat libovolný logický výraz, například

not (a or b) = (((a nand a) nand (b nand b)) nand ((a nand a) nand (b nand b))).

Vaším úkolem je napsat program, který danou logickou funkci F přepíše pomocí operace nand. Pro počítač budeme ovšem logické operace zapisovat pomocí standardních ASCII znaků takto: ∧ → *, ∨ → +, not → !, ⇒→ >, ≤→ <, nand → &, nor → |, xor →^.

Řešení

8-3-5 Konečně automaty (15 bodů)

A nakonec pokračování seriálu o konečných automatech – další dva jazyky (ten druhý je o něco obtížnější):

Příklad: První jazyk obsahuje slovo ababbab a neobsahuje babbaba, druhý obsahuje 11110000 a neobsahuje 11000 ani 1110001.

Řešení