První série osmého ročníku KSP

Zadání úloh

8-1-1 Rozděl a panuj (10 bodů)

Zlatá horečka postihla skupinu N zlatokopů, kteří se vydali rýžovat zlato na Aljašku. Rýžovali a rýžovali a rýžovali, až nakonec získali N2 valounů zlata v hodnotě od 1 do N2 tolarů.

Nu a přišlo dělení a jelikož zlatokopové jsou horké hlavy a jsou trochu hloupí, je potřeba zlato mezi ně spravedlivě rozdělit tak, aby každý dostal zlato se stejnou hodnotou a aby měl každý též stejný počet valounů.

Navrhněte tedy algoritmus a napište program, který pro dané N najde rozdělení hodnot 1 až N2 do N skupin tak, aby součet hodnot byl ve všech skupinách stejný.

Řešení

8-1-2 Sedlový bod (10 bodů)

Mějme matici A celých čísel o velikosti M ×N. Sedlovým bodem takovéto matice je prvek aij takový, že je maximální ve svém sloupci a minimální ve svém řádku. Řečeno slovy matematika:

pro všechna  k, l  (1 ≤ k ≤ M, 1 ≤ l ≤ N)  platí:  akj ≤ aij ≤ ail.

Navrhněte algoritmus a napište program, který pro zadanou matici určí, zda má nějaký sedlový bod a v případě, že ano, vypíše souřadnice alespoň jednoho sedlového bodu.

Řešení

8-1-3 Klíč (13 bodů)

Všichni jistě víte, jak vypadá klíč. Klíč je popsán celými čísly N, M, L, R a (N+1)-ticí nezáporných celých čísel Y0, … , YN, pro kterou platí:

Obrázek klíče

A teď úloha: Navrhněte algoritmus a napište program, který určí počet všech různých klíčů, je-li dáno M, N, L, R.

Poznámka: Tato úloha pochází původně z dílny zámečnického mistra Čílka, ovšem v současné době se touto otázkou zabývají i některé skupiny z podsvětí.

Řešení

8-1-4 MIDI (11 bodů)

MIDI (Musical Instrument Digital Interface) je standard pro komunikaci mezi počítačem a elektronickými hudebními nástroji. Část tohoto standardu definuje příkazy, které ovládají zapínání a vypínání jednotlivých tónů na hudebním nástroji. Tyto příkazy se sestavují do sekvencí (programů), kdy každý příkaz má vyznačen čas, ve kterém se má provést. Jednotlivé příkazy jsou uspořádány vzestupně podle svého času.

Pro zapnutí resp. vypnutí generování tónu slouží příkaz ON resp. OFF, za nímž následuje číslo noty, jíž se to týká.

Například následující MIDI program odpovídá současnému spuštění tří tónů (60, 70 a 80) po dobu 10 časových jednotek a následného spuštění tónu 62 po dvě časové jednotky:

 0 ON  60
 0 ON  70
 0 ON  80
10 OFF 60
10 OFF 80
10 OFF 70
10 ON  62
12 OFF 62

Většina existujících skladeb nemůže být přímo přepsána do MIDI programu, neboť občas je již daný tón spuštěn, když se v původní skladbě požaduje jeho opětné zaznění. Například:

 0 ON  60
10 ON  60
12 OFF 60
20 OFF 60

Syntezátor bude tento program interpretovat tak, že nechá zaznít tón 60 na 12 časových jednotek a ne na 20, jak jsme předpokládali. Neuslyšíme tedy oddělené zaznění dvou tónů 60, neboť zapnutí tónu, který je již zapnut, nemá žádný efekt.

Pokud je tedy tón již zapnut a v programu je příkaz ON, aby tón zazněl znovu, je třeba do programu vložit vypnutí onoho tónu jednu časovou jednotku před tímto druhým spuštěním. Zároveň je potřeba odstranit příkaz pro vypnutí tohoto tónu, který následuje jako nejbližší. Takový program bude již interpretován jako dvojité následné zaznění tohoto tónu.

Dalším problémem je vypnutí a zapnutí tónu ve stejný časový okamžik. V tomto případě záleží na pořadí příkazů ON a OFF uvedených v programu, zda tón bude znít nebo ne. Například srovnej následující programy:

 0 ON  60              0 ON  60
10 ON  60             10 OFF 60
10 OFF 60             10 ON  60
20 OFF 60             20 OFF 60

V levém programu se tón 60 vypne již v čase 10. V pravém programu je naproti tomu zase čas, kdy je tón vypnut, nedostatečný, aby jej lidské ucho postřehlo. V obou případech se pro úpravu programu použije stejné řešení – přesune se první příkaz OFF o 1 časovou jednotku před druhé ON.

Pokud OFF vložené jednu časovou jednotku před ON nastává ve stejný okamžik jako jiné ON, pak vložené OFF a po něm následující ON budou z programu zcela vyjmuty.

Vaším úkolem je napsat program, který přečte MIDI program v textové podobě a upraví jej dle námi popsaných pravidel.

Řešení

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

Do tohoto ročníku KSP jsme zařadili několik na sebe navazujících úloh zabývajících se konečnými automaty. Ti z vás, kteří nevědí, co to konečný automat je, naleznou podrobné vysvětlení na straně 18.

Sestrojte konečné automaty, které rozeznávají následující jazyky:

Do jazyka L1 tedy patří všechna slova, která končí na "baba". Do jazyka L2 například patří 135, 12, e, nepatří do něj např. 534, 12321, 1223.

Poznámka: Sestrojením konečného automatu rozumíme vypsání složek pětice a nakreslení obrázku podle uvedených pravidel.

Řešení