První série třetí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


3-1-1 Číselná posloupnost


Napište program, který pro zadanou posloupnost N celých, kladných i záporných čísel nalezne souvislý úsek této posloupnosti s největším součtem (souvislý znamená, že nevynecháte žádné číslo mezi začátkem a koncem vybraného úseku). U této úlohy je důležitý důkaz správnosti algoritmu.


3-1-2 Logické formule


Logický výraz je:

  • velké písmeno AZ nebo
  • (výraz1 op výraz2), kde op je jeden z operátorů &, ^, >, =, které mají postupně význam „a zároveň“, „nevylučovací nebo“, „implikace“, „ekvivalence“, případně
  • -výraz, kde - znamená negaci logického výrazu.
Napište program, který libovolný logický výraz převede na logický výraz obsahující pouze operátor @ s významem „negace a zároveň“ (tzn. A@B neplatí, pokud platí A a B, A@B=-(A&B) ).

Příklad: ((A^B)&-C) = ((A@(C@C))@(B@(C@C))).


3-1-3 Tenisový turnaj


Je dáno rozlosování n=2k tenistů na základní nulté úrovni turnaje. Je dána matice vzájemných sil hráčů:

1 pokud i porazí j
aij= 0 není-li jasný výsledek
-1 pokud j porazí i.

Napište program, který přečte rozlosování hráčů (permutaci čísel 1… n) a pro zadanou tabulku aij vytiskne čísla hráčů, kteří mohou při daném rozlosování vyhrát.

Příklad pro k=2: Je dána matice

a=
( * 1 0 -1 )
-1 * -1 -1
0 1 * 1
1 1 -1 *

a rozlosování 1, 3, 2, 4 (tzn. v prvním kole spolu hrají 1 se 3, 2 se 4). Možnými vítězi jsou hráči 3 a 4.


3-1-4 Systém menu


Tak jako loni i letos bychom rádi vždy alespoň jednu úlohu série věnovali nějakému praktickému problému. Tentokrát jsme se rozhodli potýrat vás souborem procedur a funkcí, které umožní snadnou realizaci menu ve vašich programech.

Menu je seznam položek, řazených vertikálně nebo horizontálně. Aktuální položka je zvýrazněna a její změna se provádí pomocí šipek nahoru, dolů (příp. doleva, doprava). Výběr položky a opuštění menu se provede klávesou ENTER. Při stisku klávesy ESC se obnoví případná nastavená aktuální položka a menu se opustí.

Vytvořte si datové struktury, které vám umožní uchovávat veškeré informace o jednotlivých menu, jež považujete za užitečné. Sestavte procedury a funkce, které vám umožní zobrazení příslušného menu, jeho smazání, obsluhu zvoleného menu (pohyb kurzoru v něm a zvýraznění zvolené položky). Případným dalším nápadům se meze nekladou. Vzhledem k tomu, že program bude vyžadovat komunikaci s obrazovkou a že tuto komunikaci chceme poněkud znormalizovat, můžete pro vstup a výstup používat pouze následující procedury a funkce:

  • GetKey:integer – čeká na stisk klávesy a vrátí některou z číselných konstant UP, DOWN, LEFT, RIGHT, ENTER, ESC. Jejich význam v uvedeném pořadí je: pohyb kurzoru v menu nahoru, dolů, doleva, doprava, výběr položky a opuštění menu, opuštění menu beze změn.
  • CPrint(Co:String;BarvaTisku,BarvaPozadi:integer) – na aktuální pozici kurzoru vytiskne řetězec Co.
  • ScreenWidth:integer – vrací šířku obrazovky ve znacích.
  • ScreenHeight:integer – vrací výšku obrazovky ve znacích.
  • GotoXY(x,y:integer) – jsou-li data platná (to jest současně platí 1 ≤ xScreenWidth a 1≤ yScreenHeight), nastaví kurzor na příslušnou pozici na obrazovce, levý horní roh je (1,1).
  • ClrScr(Barva:integer) – vymaže obrazovku zadanou barvou.
  • Store(xl,yh,xp,yd:integer):^integer – funkce uloží text ze zadané části obrazovky (obdélník s levým horním rohem (xl,yh) a pravým dolním rohem (xp,yd)) do paměti a vrátí ukazatel na její začátek; jsou ukládány jak znaky, tak jejich barva.
  • Recall(xl,yh,xp,yd:integer;Uk:^integer) – vytiskne na dané místo na obrazovce text uložený funkcí Store; Uk je ukazatel na začátek paměti, kde je text uložen.