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

Zadání úloh

8-2-1 O líných novinářích (12 bodů)

Lidé jsou leniví a tato vlastnost se nevyhýbá ani mnohým novinářům. Někteří novináři jsou dokonce tak líní, že do svých článků píší některé pasáže vícekrát, aby lehce dosáhli požadované délky textu. Šéfredaktor proto potřebuje program, který pro daný text článku zjistí nejdelší úsek, jenž se v něm opakuje.

Navrhněte tedy algoritmus a napište program, který pro daný text délky maximálně 1000 znaků zjistí nejdelší úsek, v něm se opakující. V případě, že maximálních podúseků je více, nalezněte všechny.

Řešení

8-2-2 Rozmarná princezna (11 bodů)

V jednom království si rozmarná princezna vymyslela, že si každý večer s někým zahraje hru nim a pokud dotyčný prohraje, půjde spát na noc do chlívku. Přes týden, kdy byli protihráči z práce unaveni, se hrála jednodušší varianta, v neděli pak těžší.

Jednodušší varianta hry má tato pravidla: na stůl se položí n sirek, kde n je nějaké kladné celé číslo. Poté střídavě hráči odebírají jednu, tři nebo pět sirek. Kdo odebere poslední sirku, vyhrál.

Těžší varianta má obdobná pravidla, ovšem lze odebrat pouze počet sirek, který odpovídá libovolné mocnině čísla 2, tj. 1, 2, 4, 8, …

Zda začíná odebírat princezna nebo její protihráč, určí se losem.

Naším úkolem je pomoci protihráči princezny, tj. pro oba druhy hry nim navrhnout vhodnou strategii hry a napsat program, který se jí bude řídit tak, aby protihráč, pokud je to možné, vyhrál.

Řešení

8-2-3 U zeleného stromu (10 bodů)

V holičství "U zeleného stromu" bylo 2N+1 stoliček, na nichž sedělo N trpaslíků a N hobitů a zbylá stolička byla prázdná. Stoličky byly vyrovnány do řady a očíslovány čísly 1 až 2N+1. Holič bral na ostříhání zákazníky v pořadí, v jakém seděli na stoličkách.

Ježto hobiti jsou známí svou mírnou povahou a tím, že nikam nespěchají, požádal občas holič čekající zákazníky, aby si povyměňovali místa tak, aby všichni trpaslíci seděli na stoličkách před hobity. A aby během vyměňování nevznikl zmatek, muselo to probíhat tak, že se vždy někdo zvedl a sedl si na volnou stoličku. V okamžiku, kdy bylo dosaženo kýženého cíle, tedy trpaslíci seděli před hobity, pokračoval holič ve své práci. Jelikož trpaslíci byli nedočkaví, přemýšleli, jaké musí být pořadí při vyměňování, aby celá operace proběhla na co nejmenší počet přesunů.

A právě vaším úkolem je navrhnout algoritmus a napsat program, který pro dané rozmístění N hobitů a N trpaslíků na 2N+1 stoličkách určí, v jakém pořadí má dojít k výměnám, aby byl počet výměn nejmenší možný.

Řešení

8-2-4 Náhrdelník (10 bodů)

Rozmarná princezna z předešlé úlohy nosí na krku náhrdelník z perel. Jelikož se jí často stane, že se jí při hře na zahradě náhrdelník rozsype, očíslovala si perly čísly od jedné do N. Vždy když se jí pak náhrdelník rozsype, musí sluhové perly posbírat, zjistit, zda nějaká nechybí a pak jej znovu svázat. Často se stane, že chybí právě jedna perla. Pak ji musí sluhové hledat tak dlouho, dokud ji nenajdou, přičemž hledají perlu s konkrétním číslem a jiné nalezené perly si mohou ponechat.

Vaším úkolem je navrhnout algoritmus a napsat program, který pro dané N a neuspořádanou posloupnost čísel jedna až N zjistí, zda některé číslo v posloupnosti chybí a v případě, že ano, tak které. Chybějící číslo je maximálně jedno a žádné číslo se v posloupnosti neopakuje.

Příklad: N=7, posloupnost { 4,2,3,5,1,7 }. Chybí perla číslo 6.

Řešení

8-2-5 Konečné automaty (10 bodů)

Připravili jsme pro vás další dva jazyky, pro které byste měli sestrojit konečné automaty. Jeden z nich je o něco snazší, druhý z nich je obtížnější.

Příklad: První jazyk například neobsahuje slova baba, ababab, bbbbbababbbb a další, druhý obsahuje slova baba, abba, bababba, aaaabba a další.

Řešení