Čtvrtá série desátého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 25. dubna 1998. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru 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.

Řešení


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].

Řešení


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í

z1… zi-1 zr … zs zj+1… zr-1 zi … zj zs+1 … zn.

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ý'.

Řešení


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.

Řešení