První série páté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

5-1-1 Anagramy

Dvě slova jsou svými přesmyčkami (anagramy), obsahují-li tatáž písmena v jiném pořadí. Např. slovo JAKUUB je přesmyčkou slova BUUKAJ (a naopak), zatímco slovo BAKUJ nikoli. V zadaném souboru je „slovník“ – cca 100 000 nejvýše desetiznakových slov, jež nejsou uspořádána podle abecedy. Navrhněte algoritmus a napište program, který upraví slovník do takového tvaru, abyste zástupům chtivých hádankářů mohli za tučný obolus promptně (= rychle) zodpovídat dotazy typu: Jaké přesmyčky slova XYZ se ve slovníku vyskytují? Místa na disku je k dispozici dost (nejméně na tři další slovníky stejné velikosti).

Nápověda: Na jedné americké univerzitě žije profesor, který umí vysvětlit jedno z efektivních řešení této úlohy pomocí několika máchnutí levou rukou a tří slov. (Pro nechápavé pak musí občas přidat ještě jedno.)

5-1-2 Za nezávislost!

Nezávislou množinou obdélníků řádu Max, kde Max je kladné celé číslo, nazvěme takovou množinu obdélníků M, že není možné (ani po libovolném pootočení) žádný z obdélníků z M vložit do jiného obdélníku z M tak, aby nepřečuhoval, a že délky stran všech obdélníků v M jsou kladná celá čísla menší než Max. Např. množina obsahující obdélníky s délkami stran (10,3, )(5,7) a (6,6) je nezávislá (řádu např. 11), zatímco množina s obdélníky (10,3, )(5,7) a (3,7) nikoli. Navrhněte algoritmus a napište program, který pro zadaná kladná celá čísla n, Max vytiskne délky stran obdélníků všech dvouprvkových, trojprvkových, …, až n-prvkových nezávislých množin obdélníků řádu Max. Ze všech množin lišících se jen pořadím nebo pootočením obdélníků vytiskne program vždy jen jednu.

Zadání pro normální lidi: Vytiskněte délky stran (dvojic, trojic, …) obdélníků, z nichž se žádný nedá vložit do nějakého jiného.

Příklad: Pro n=3 a Max=6 program vytiskne (kupříkladu) tyto dvojice a trojice:

(3,2) (4,1) (1,5) (2,2) (1,4) (2,2) (1,5) (4,3)
(2,4) (3,3) (5,3) (4,4) (4,4) (5,1) (1,4) (3,3)
(5,2) (4,4) (1,5) (3,2) (2,5) (3,3) (1,5) (2,4)
(3,3) (1,5) (1,3) (2,2) (3,4) (2,5) (1,5) (2,4) (3,3)

5-1-3 Čekání^k

Je dáno pole n prvků. V budoucnu bude třeba o postupně přicházejících k prvcích zjišťovat, zda se vyskytují mezi prvky pole. Vhodně se na to připravte. Navrhněte nejlepší řešení vzhledem k hodnotám n, k. Součástí řešení nemusí být program.

5-1-4 Podraz

Je dáno celočíselné pole A[1… MaxN]. Napište co nejrychlejší proceduru, která pro zadané číslo n (1≤ n ≤ MaxN) určí maximální prvek úseku A[1… n].

5-1-5 Netvořky

Topologie v symetrické síti: Síť je množina počítačů (uzlů). Mezi některými dvojicemi uzlů existuje obousměrné spojení. Každý uzel zná svou jednoznačnou identifikaci (nějaké číslo, které získá zavoláním systémové funkce get_node_id() ) a všechny své bezprostřední sousedy a umí jim všem poslat zprávu.

Navrhněte a nějakým rozumným způsobem zapište algoritmus, jehož provedením na všech uzlech sítě získá každý uzel mapu nejkratších spojení od sebe do všech ostatních uzlů. Vzdálenost mezi uzly x, y je dána minimálním počtem přechodů mezi uzly potřebných k dopravě zprávy z uzlu x do uzlu y.