Třetí 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-3-1 Konvexní mnohostěn
Mnohostěn je zadán výčtem vrcholů a seznamy vrcholů jednotlivých stěn. Napište program, který u zadaného mnohostěnu zjistí, zda je konvexní. Vstupem je počet vrcholů a posloupnost jejich souřadnic. Dále je na vstupu počet stěn a pro každou stěnu jsou zadány seznamy pořadových čísel vrcholů této stěny. Např. čtyřstěn je popsán seznamem vrcholů 1, 2, 3, 4 a seznamy vrcholů v jednotlivých stěnách: 1,2,3; 2,3,4; 1,2,4; 1,3,4.
3-3-2 Cesty v grafu
Orientovaný graf o n vrcholech, n≥ 2, je zadán maticí A:array [1… n,1… n] of boolean, kde A[k,l] je true právě tehdy, když existuje přímé spojení (hrana) z vrcholu k do vrcholu l. To, že jde o orientovaný graf znamená, že nemusí být nutně A[k,l]=A[l,k]. Napište program, který pro zadanou matici A a vrcholy i, j, i ≠ j, určí maximální počet navzájem disjunktních cest vedoucích z i do j. Tím se rozumí hledat cesty z i do j tak, aby se jich do grafu najednou „vešlo“ co nejvíc; disjunktní jsou přitom takové cesty, které s výjimkou i, j neobsahují stejné vrcholy.
3-3-3 Spojení bodů
Je dána množina bodů v rovině. Napište program, který vytvoří uzavřenou lomenou čáru nikde neprotínající sebe sama, jejíž vrcholy tvoří právě všechny body dané množiny a jejíž délka je minimální. Vstupem je počet bodů n, n ≥ 3 a posloupnost x1 y1, x2y2, … , xnyn souřadnic bodů množiny. Výstupem je posloupnost indexů i1… in bodů; přitom body s indexy ik, ik+1 jsou sousedními na vygenerované lomené čáře, stejně tak body s indexy 1 a n.
3-3-4 Textový procesor
Napište program, který přečte ze vstupu text s řídicími symboly a vytiskne jej na tiskárnu v zadaném formátu. Text obsahuje písmena, číslice a znaky s ASCII kódem větším nebo rovným 32. Dále obsahuje posloupnosti řídicích symbolů začínající vždy některým znakem s ASCII kódem od 0 do 7. Některé posloupnosti jsou jednoznakové, jiné dvouznakové nebo mají proměnnou délku. Následující tabulka uvádí význam těchto posloupností a jejich délku. Posloupnosti jsou seřazeny podle kódu svého počátečního znaku:
- 0 Lo Po Zar T P1 …PT – délka 5+T znaků
Nastavení formátu textu:- Lo – velikost levého okraje textu ve znacích od levého okraje stránky
- Po – velikost pravého okraje textu ve znacích od pravého okraje stránky
- Zar – nastavení zarovnávání textu: 0=vypnuto, 1=zapnuto
- T – počet nadefinovaných tabulátorů
- Pi – poloha i-tého tabulátoru od levého okraje stránky
- 1 – délka jeden znak
Označuje konec řádku a přechod na nový řádek. - 2 Zar – délka dva znaky
Nastavení zarovnávání textu:- Zar – 0=vypnuto, 1=zapnuto
- 3 – délka jeden znak
Označuje pevnou mezeru. Slova oddělená pouze pevnou mezerou se chápou jako jedno slovo, nelze mezi ně vkládat mezery při zarovnávání ani je dělit na různé řádky. - 4 – délka jeden znak
Označuje možné rozdělení slova. Pokud je slovo uprostřed řádku, znak se netiskne. Pokud slovo přesahuje přes okraj textu a část slova do znaku 4 se na původní řádek vejde, provede se rozdělení slova na dva řádky s vložením pomlčky. - 5 – délka jeden znak
Označuje zarovnávání doprava. Text od tohoto znaku do prvního znaku 1 nebo 7 je zarovnán k pravému okraji. Pokud se na řádek tento text nevejde (je moc dlouhý a přepsal by již napsaný text), pak se vezme největší možný počet slov, který lze napsat, a zarovná se k pravému okraji. Další řádek se již píše normálním způsobem. - 6 – délka jeden znak
Označuje vycentrování následujícího textu. Text od tohoto znaku do prvního znaku 1, 5 nebo 7 je umístěn uprostřed mezi okraje. Pokud to nelze provést (už je tam nějaký text napsán), pak se tento kód ignoruje. - 7 – délka jeden znak
Označuje tabulátor. Poloha tabulátorů je uložena ve formátu textu. Po znaku tabulátor se následující text začíná psát napravo od pozice prvního tabulátoru, nalezeného vpravo od aktuální pozice. Pokud žádný takový tabulátor neexistuje, tento znak se ignoruje.
Toto je úplný seznam řídicích znaků, které ovlivňují výsledný vzhled textu. Pokud slovo přesahuje přes pravý okraj, je automaticky přesunuto na další řádek. Pokud je na řádce pouze toto slovo (jedná se o slovo delší než jeden řádek), pak se slovo přeruší a tisk pokračuje na nový řádek. Zarovnávání se provádí rovnoměrným vkládáním mezer mezi slova tak, aby konec posledního slova na řádce byl zarovnán s pravým okrajem textu.