Čtvrtá série desátého ročníku KSP
- Termín série: 25. dubna 1998
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak sepsat řešení: viz Návod na teoretické úlohy
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
Zadání úloh
10-4-1 Wagón klád (10 bodů)
Ve wagónu je ohromné množství tyčí různých délek. Vy potřebujete zjistit, jaké všechny délky jdou z těchto tyčí sestavit. Máte však málo lepidla, takže nemůžete spojovat dohromady více než dvě tyče. Vrchní královský dřevolepič po vás chce, abyste napsali program, který tuto úlohu vyřeší, navíc ovšem žádá, abyste každou délku oznámili právě jednou.
Ovšem celé to má ještě jeden háček: tyčí je tolik, že jste rádi, že se vám vejde do paměti seznam jejich délek – na to, aby se vám tam vešel seznam součtů dvojic, není ani pomyšlení.
Příklad: Pro seznam 1,2,3 je správným výsledkem 2,3,4,5,6.
10-4-2 DĚLITEL (11 bodů)
Činíme další pokus odradit vás od řešení KSP za pomoci Turingových strojů: Zkuste sestrojit Turingův stroj hledající pro daná dvě celá kladná čísla x a y jejich největšího společného dělitele [x,y] – tedy největší přirozené číslo takové, které je dělitelem jak x, tak y.
Hodnotí se nejen funkčnost, ale i rychlost výpočtu. Nezapomeňte spočítat i časovou a paměťovou náročnost svých strojů.
Nápověda: Uvědomte si, že platí:
- [x,y] = [y,x]
- [x,y] = [x-y,y]
- Je-li x sudé a y liché, [x,y]=[x/2,y].
- Jsou-li x i y sudá, [x,y]=2·[x/2,y/2].
10-4-3 Sssssstttttrrrriiinng (10 bodů)
Mějme velice dlouhý řetězec znaků z1… zn, dokonce tak dlouhý, že se nám mimo něj vejde do paměti už jen krátký program a několik málo pomocných proměnných. A nyní jsme se rozhodli, že uvnitř řetězce prohodíme dva nestejně dlouhé nepřekrývající se substringy zi… zj a zr… zs (1 ≤ i≤ j < r ≤ s ≤ n) – což znamená přerovnat znaky do pořadí
Zkuste to s danou pamětí v co nejkratším čase provést.
Přiklad: Pro string `neceločíselný', i=3, j=5, r=7, s=12
je kýženým výsledkem `nečíselnocelý'.
10-4-4 Duraloví dravci (11 bodů)
V Absurdistánu měli N měst spojených navzájem leteckými linkami S různých dopravních společností. Ale jak již to v tomto státě bývá, byrokracie se rozmohla tak, že i policisté hlídkovali jezdíce na úředním šimlu, a proto každá dopravní společnost měla různé tarify za překlad nákladu z letadel různých jiných společností. Vám přinesli následující tabulky:
- p(s,i,j) – cena účtovaná společností s za přepravu vašeho nákladu z města i do města j. ∞, pokud taková letecká linka neexistuje.
- m(i,r,s) – cena účtovaná za přeložení nákladu z letadla společnosti r do letadla společnosti s v městě i. ∞, pokud tomu úřední předpisy brání.
Máte vyřešit, jak svůj náklad co nejlevněji přepravit z města 1 do města N.