Čtvrtá 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-4-1 Bo Bulkovy tramvaje

Výhybka je zařízení, které se může nacházet ve dvou stavech. Jako její reprezentaci proto užíváme nejčastěji logickou proměnnou se stavy {0,1}. Křižovatka K je určena množinou výhybek, které ji tvoří (značíme VK) a množinou čísel tramvajových linek, které jí projíždí. Její okamžitý stav je popsán hodnotami výhybek, které jsou prvkem VK. Tramvajová linka je vzhledem ke křižovatce K určena svým číslem a výhybkovým vzorcem. Výhybkový vzorec je množina výhybek (značíme FKt, kde t je číslo příslušné tramvajové linky; FKt je podmnožinou VK) a zobrazení h z FKt do {0,1}. Její význam je ten, že všechny výhybky v, které jsou prvkem FKt, se po průjezdu tramvaje t křižovatkou K nacházejí ve stavu h(v). Stav ostatních výhybek (tj. těch, které nejsou prvkem FKt), se po průjezdu tramvaje t nemění.

Úlohy:

  1. Vytvořte datové struktury, které umožní uchovávat informace o křižovatkách a tramvajových linkách.
  2. Napište program, který pro zadanou křižovatku určí tramvaj (nebo tramvaje), která jí mohla projíždět jako poslední, předposlední, předpředposlední, …, pro libovolné zadané n; pro n=1 určujete poslední, pro n=2 předposlední atd. projíždějící tramvaj. Přitom znáte aktuální stav křižovatky a veškeré údaje týkající se tramvají touto křižovatkou projíždějících.

3-4-2 Lucasova úloha

Je dáno přirozené číslo n>0. Na hracím plánu, který je tvořen 2n+1 poli uspořádanými do řady, je rozmístěno n černých a n bílých hracích kamenů tak, že na každém poli stojí nejvýše jeden kámen. Tahem rozumíme přemístění kamene z jednoho pole na jiné při dodržení všech následujících pravidel:

  1. Kámen lze přemístit pouze na pole, které není obsazeno jiným kamenem.
  2. Kámen lze přemístit pouze na sousední pole, anebo „ob jedno“ pole („přeskočit“ jedno pole).
  3. Bílý kámen lze přemístit pouze na pole nacházející se od jeho současné pozice vpravo, černý kámen naopak jen vlevo.
Ve výchozí pozici stojí všechny bílé kameny v levé části hracího plánu, černé v pravé části, prostřední pole je prázdné. Koncová pozice je symetricky obrácená (tzn. bílé kameny jsou vpravo, černé vlevo). Vaším úkolem je napsat program, který pro zadanou pozici určí, zda je korektní (tzn. zda je možné dosáhnout jí konečnou posloupností tahů z výchozí pozice) a zda je řešitelná, tzn. zda lze z této pozice dosáhnout koncové pozice konečnou posloupností tahů.

3-4-3 Ekonomická cesta

Je dán výčet měst a linek autobusů mezi těmito městy. Napište program, který najde nejlevnější cestu mezi městy A a B, která celá trvá nejvýše jeden den. Vstupem programu jsou města A, B a jízdní řád, tj. seznam autobusových linek. U autobusové linky je pro každé město uvedeno, zda autobus v tomto městě staví či nestaví. Pokud zde autobus staví, je navíc zadán čas příjezdu, odjezdu a cena jízdenky od počáteční stanice. Cena jízdenky mezi dvěma městy se vypočte jako rozdíl cen jízdenek od počáteční stanice. Pokud jezdí autobus přes půlnoc, jsou časy z druhého dne v intervalu 24–48 hod.

3-4-4 České třídění

Nejprve několik definic: Řetězcem rozumíme posloupnost znaků. Dva řetězce se rovnají, pokud mají stejnou délku a znaky na odpovídajících pozicích jsou stejné. Jsou-li oba řetězce stejně dlouhé a nerovnají se, postupujeme při určování jejich vzájemného vztahu podle následujícího algoritmu: Postupujeme v obou řetězcích současně, dokud nenarazíme na navzájem různé znaky. Jelikož hláska `ch' je kódována dvěma znaky, vždy po načtení `c' musíme zjistit, zda bezprostředně nenásleduje `h' a pokud ano, je třeba celé `ch' chápat jako jeden znak a tak s ním i zacházet. Pokud tyto znaky nejsou ve stejné skupině (tj. nejsou-li v tabulce uvedeny společně v hranatých závorkách), je výsledek porovnání řetězců shodný s výsledkem porovnání těchto znaků (podle tabulky na konci zadání). Jsou-li ve stejné skupině, je třeba najít nejbližší další výskyt znaků z různých skupin a podle nich rozhodnout. Liší-li se řetězce jen ve znacích ležících ve stejné skupině, teprve pak se rozhoduje podle pořadí uvnitř skupiny.

Napište funkci, která dostane na vstupu dva řetězce a vrátí výsledek jejich porovnání podle tohoto schématu:

0 řetězce jsou stejné
c(s1,s2) = 1 první řetězec je větší
-1 první řetězec je menší.

Nezapomeňte na to, že hláska `ch' se kóduje dvěma znaky, ale při porovnávání se s ní zachází jako s jediným znakem! Pořadí v české abecedě je takovéto:

[a<á]<b<c<č<[d<ď]<[e<é<ě]<f<g<h<ch<[i<í]<
<j<k<l<m<[n<ň]<[o<ó]<p<q<r<ř<s<š<[t<ť]<
<[u<ú<ů]<v<w<x<[y<ý]<z<ž

Velké písmeno je vždy „menší“ než jemu odpovídající malé písmeno. Algoritmus by měl být nezávislý na vnitřním kódu počítače. Pokud by vám to připadalo příliš obtížné, můžete použít vlastností ASCII kódu, ve kterém máte uspořádané zvlášť znaky velké a zvlášť malé anglické abecedy a přidané české znaky jsou neuspořádaně kódovány v horní polovině tabulky.