První série šestého ročníku KSP

Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.

Zadání úloh

6-1-1 Volejbalová síť

Jistě všichni znáte volejbalovou síť. Po čase, když ji dost dlouho používáte, se taková síť začne rozpadat, trhají se jednotlivé uzly. Vaším úkolem bude zjistit, jestli je taková síť ještě jakžtakž použitelná, tj. jestli její horní rohy jsou ještě stále spojené.

Rozměrem sítě budeme rozumět počet uzlů ve svislém a ve vodorovném směru n ×m. Jednotlivé uzly budeme značit jejich souřadnicemi počítanými od nuly, shora dolů, zleva doprava. Vstupem programu pak budou souřadnice zničených uzlů. Úkolem bude zjistit, zda síť je použitelná, tj. zda existuje cesta z uzlu [0,0] do uzlu [0,m-1] přes neporušené uzly. Cesta je posloupnost uzlů, kde dva po sobě jdoucí uzly mají vždy jednu souřadnici stejnou a druhá se liší o 1.

Příklad: Síť 2×3 s porušenými uzly [0,1] a [1,1] je nepoužitelná a program nám proto ohlásí „Je nepoužitelná“, naproti tomu např. síť 2×4 s porušenými uzly [1,0] a [1,3] je použitelná a program nám tedy ohlásí „Je použitelná“.

6-1-2 Družice

Družice vysílá zprávy a my na Zemi je přijímáme. Zprávy jsou však vlivem šumů zkresleny. Naštěstí nám však družice zprávu vždy několikrát zopakuje. Naneštěstí ale nevíme kolikrát ani jak je zpráva dlouhá, ale víme, že poslední opakování nemusí být ukončené, tj. při posledním opakování může odvysílat jen začátek. A naším úkolem je napsat program, který ze zachyceného textu určí původní obsah zprávy.

Vstupem programu je tedy řetězec znaků. V tomto řetězci je několikrát po sobě (minimálně třikrát) stejná zpráva, avšak některé znaky v jednotlivých exemplářích zprávy byly nahrazeny zcela náhodnými znaky. Výstupem programu pak bude nejpravděpodobnější obsah původní zprávy.

Poznámka: Pravděpodobnost správnosti obsahu zprávy je počet správných znaků na správném místě zachyceného textu dělený jeho délkou.

Příklad: Zachycený text abxdefancdefabcdwfab obsahuje zprávu abcdef, což bude výstup vašeho programu.

6-1-3 Plody

Řekneme, že řetězec P je plodem řetězce S, jestliže se P dá vytvořit z S použitím následujících pravidel:

  1. každý znak ? (otazník) v S se nahradí libovolným znakem různým od otazníku a hvězdičky.
  2. každý znak * (hvězdička) v S se nahradí libovolnou (i prázdnou) posloupností znaků různých od otazníku a hvězdičky.
Napište program, který přečte ze vstupu řetězce S a P a zjistí, zda P je plodem S.

Příklad: Řetězce FRANTA, FRANTARANTA, FERON jsou plodem řetězce F*R?N*, zatímco řetězce FRNAK, FREON nejsou.

6-1-4 Marijáš

Každý, kdo už někdy držel v ruce karty, byl postaven před úlohu, jak si karty co nejrychleji a co nejsnáze v ruce srovnat. Karty se rovnají tak, že se vezme m po sobě jdoucích karet počínaje n-tou, ty se z vějíře karet vyndají a přemístí se na jiné místo ve vějíři. Nejrychlejší srovnání je tedy takové, které se provede pomocí minimálního počtu vytažení bloku karet. A právě na pomoc začínajícím karbaníkům máte napsat program, který takový postup najde.

Vstupem programu bude permutace čísel 1 až n – rozdávka karet. Výstupem programu bude posloupnost trojic čísel, která udává optimální rovnání, tj. bude co nejkratší. První číslo v trojici udává, kterou kartou blok začíná (ne hodnota, ale pozice), druhé kolik karet přenášíme a třetí, kam je zařadíme, tj. za kterou kartu (opět pozici) ve zmenšeném vějíři.

Příklad: Pro vstup 1,2,5,3,7,4,6 nám program vypíše [4,3,2], [4,1,6].