První série devátého ročníku KSP

Zadání úloh

9-1-1 Cesta kulhavého koně (10 bodů)

Bylo-nebylo. Na jedné šachovnici žil kulhavý kůň. Je to poněkud neobvyklá figurka, ale její jméno trefně vystihuje, jakých tahů je schopna: pohybuje se na šachovnici v liché tahy jako kůň (v jedné ze souřadnic o jedno pole, v druhé o dvě), v sudé jako král (v každé souřadnici o nejvýše jedno pole) – v prvním tahu tedy táhne jako kůň, v druhém jako král, ve třetím jako kůň atd.

Vaším úkolem je navhrnout algoritmus a napsat program, který pro danou velikost šachovnice (M ×N) a dané souřadnice dvou políček (levé dolní políčko má souřadnice [0,0], pravé dolní [M-1,0] a levé horní [0,N-1]) zkonstruuje nejkratší cestu, kterou může kulhavý kůň dojít z výchozího políčka na cílové, a vypíše souřadnice všech touto cestou navštívených polí (nejkratší cesta je ta, jež jich navštíví nejméně).

Řešení

9-1-2 Kupec Bengálský (8 bodů)

Starý pirát Cor Sair odešel do výslužby a usadil se v malé přístavní vísce kdesi na zapadlém pobřeží. Jako odměnu za své služby dostal od svých druhů devět dělových koulí, z nichž jedna byla prý uvnitř plná zlata ukrytého na horší časy.

Po několika letech se Cor Sair rozhodl, že zlatou kouli vypátrá a ostatních se nějak zbaví – zavazily mu totiž v jeho skrovné chaloupce. Záhy se dovtípil, že se to snadno pozná podle hmotnosti – železné koule by měly vážit všechny stejně, zlatá pak o poznání více. Jediné váhy ve vsi měl ovšem hokynář Mer Chant. Když za ním pirát přišel, seznal, že klepy se šíří rychle a kupec tuší, že jedna z koulí by mohla ukrývat bohatství, a ve své zištnosti žádá za každé zvážení na svých rovnoramenných vahách tři z koulí (splatné po konci vážení), domnívaje se, že se tak domůže všech koulí dříve, než pirát stačí zjistit, která vlastně je ta pravá.

Cor Sair se ovšem nenechal nachytat a přes tyto náročné podmínky vymyslel postup zaručeně vedoucí ke zjištění oné zlaté koule, aniž by ji musel obchodníkovi odevzdat (a to dokonce bez použití násilí). Dokážete to také vy? (Na rovnoramenných vahách se váží tak, že nějaké koule položíme na levou misku, nějaké na pravou a dozvíme se, která miska je těžší. Obchodníkova závaží jsou nepoužitelná, poněvadž jsou příliš lehká.)

Řešení

9-1-3 Strašidlóóó (10 bodů)

Město Hauntry bylo pravoúhlou sítí ulic rozděleno na M×N bloků domů, v každém z nich žil určitý počet nájemníků. Nebydlel-li v domě nikdo, záhy se tam usadila strašidla. Starosta onoho města si nechal vypracovat plán města s přesnými počty obyvatel jednotlivých domů a položil si zajímavou otázku: kde je největší obdélník složený ze samých strašidelných domů?

Na vás je, abyste sestrojili program schopný pro dané rozměry města a matici rozložení obyvatel co nejrychleji nalézt největší (tedy maximální plochu mající) obdélník v této matici složený ze samých nul.

Řešení

9-1-4 Top secret (15 bodů)

Poslední úloha každé série tohoto ročníku KSP bude nějak souviset s šifrováním. Romantická historie šifrování (viz literatura) se sice pěkně čte, ale úlohy z programování zkonstruované na jejím základě jsou nezajímavé (příliš jednoduché nebo naopak téměř neřešitelné). Proto začneme rovnou s moderními šiframi.

Velká skupina v dnešní době používaných šifer je založena na operacích s velmi velkými přirozenými čísly (např. stomístnými). Abychom vás na tuto skutečnost připravili, bude první úloha seriálu pouze "zahřívací":

Vymyslete, jak v počítači nejlépe reprezentovat velmi velká přirozená čísla, a naprogramujte procedury nebo funkce pro základní operace s nimi: sčítání, odčítání, násobení a dělení se zbytkem.

Literatura:

  1. Otokar Grošek, Štefan Porubský: Šifrovanie – algoritmy, metódy, prax, Grada 1992.
  2. Dr. Vlastimil Klíma: Utajené komunikace, seriál o šifrování v časopisu Chip, 6/94 – 12/95.

Řešení