Třetí série sedmé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

7-3-1 Úsek

Je dáno pole čísel a1 až an. Napište program, který pro zadané číslo x určí souvislý úsek tohoto pole, jehož součet je nejbližší číslu x.

7-3-2 Bukaj

Dvě slova jsou svými přesmyčkami, obsahují-li tatáž písmena, třebaže v jiném pořadí. Například slovo JAKUB je přesmyčkou slova BUKAJ (a naopak), zatímco slova KUBA a JAKUBA nikoliv. V souboru máme „slovník“ – cca 105 nejvýše desetiznakových slov, jež nejsou nijak uspořádána. Vaším úkolem je napsat program, jež si tento slovník upraví do takového tvaru, aby byl poté schopen v co nejkratším čase zodpovídat dotazy zástupu chtivých hádankářů typu: „Jaké přesmyčky slova XYZ se ve slovníku vyskytují?“

7-3-3 Grafffff

Graf je množina bodů, zvaných vrcholy, a množina hran, které (neorientovaně) spojují vždy dva z vrcholů. Vrcholy jsou ohodnoceny nějakými přirozenými čísly, každý však jiným. Například graf s množinou vrcholů

{A,B,C,D,E}

a množinou hran

{{A,C}, {B,D}, {A,B}}

může mít vrcholy ohodnocené

{(A,4), (B,1), (C,2), (D,45), (E,17)}.

Spojením dvou grafů je opět graf, ve kterém stejně ohodnocené vrcholy jsou ztotožněny. Pokud se dva vrcholy vyskytovaly v obou původních grafech a v obou grafech byly spojeny hranou, pak budou opět spojeny hranou. Pokud byly spojeny hranou některé dva vrcholy, z nichž některý (třeba i oba) se v jednom z původních grafů nevyskytoval, pak bude hrana opět i mezi těmito vrcholy. Tedy hrana se nepřenese pouze tehdy, když vrcholy byly v obou grafech a v jednom z nich však nebyly touto hranou spojeny.

Vaším úkolem je napsat program, jehož vstupem budou dva grafy, které program spojí a výsledný spojený graf vypíše. Zvolte si vhodnou vstupní a výstupní reprezentaci grafu.

7-3-4 Červený a černý

V jámě je jistý počet bílých a černých kuliček. K dispozici je dostatečná zásoba černých kuliček. Dokud jsou v jámě alespoň dvě kuličky, opakujte tento postup: Z jámy poslepu vytáhněte dvě kuličky. Jsou-li stejné barvy, odhoďte je do stoupy a do jámy vložte černou kuličku ze zásoby. Jsou-li různé barvy, odhoďte černou kuličku a bílou vraťte do jámy.

Ukažte, že tento postup skončí a zjistěte, jak závisí výsledný stav (tzn. barva poslední kuličky) na počátečních počtech kuliček.