Druhá série dvanáctého ročníku KSP

Zadání úloh

12-2-1 Osmisměrka (10 bodů)

Jistě všichni znáte křížovkářskou hříčku zvanou osmisměrka. My si ji pro účely naší úlohy lehce upravíme: Je dána sada slov a obdélník tvaru M×N složený z písmenek. Řešení osmisměrky probíhá tak, že postupně bereme jednotlivá slova ze slovníku, pro každé slovo najdeme všechny jeho výskyty v osmisměrce ve všech směrech (slovo se v osmisměrce vůbec vyskytovat nemusí) a použitá písmenka vyškrtneme (vyškrtnuté písmeno může být ale klidně použito znovu). Slovo S=s1..sl se vyskytuje na pozici a, b, pokud o[a, b] = s1, o[a+dx, b+dy] = s2, … , o[a+l*dx, a+l*dy] = sl, kde dx a dy určují jeden z osmi možných směrů – formálně tedy dx,dy∈{-1,0,1} a buď dx≠ 0 nebo dy≠ 0. Když takto probereme všechna slova, nevyškrtaná písmena čtená v přirozeném (pro průměrného středoevropana) pořadí nám dají výsledný text.

Vaším úkolem není nic snazšího, než napsat program řešící osmisměrku. Váš program si nejdříve načte slovník a ten si libovolně předzpracuje (můžete předpokládat, že slovník se vám vejde do paměti). Potom na vstup dostane jednotlivé osmisměrky. Na ně by měl v co nejkratším čase odpovídat výslednými texty. Důraz je kladen především na rychlost vyřešení jedné osmisměrky. Délka předzpracování je méně významná.

Příklad: Ve slovníku se nachází 5 slov: maso, eso, mele, sokl, lyko. Osmisměrka tvaru 4×4 vypadá následovně:

meso
esok
lyko
elly

Zbylý text je kly.

Řešení

12-2-2 Šnečí maraton (9 bodů)

Šneci se jednoho slunného léta rozhodli uspořádat maraton – tedy plaz na 42 metrů. Na start se dostavilo N závodníků. Podle pořadí, v jakém vyráželi na trať, jim byla přiřazena startovní čísla od jedné do N. I přes nepříjemnosti, jako třeba houba znenadání vyrostlá na trati nebo ztráta domečku při prudkém zatáčení, se nakonec podařilo doplazit se do cíle všem hlemýžďům. Problém ovšem je, že každý z hlemýžďů si pamatuje pouze to, kolik soupeřů s nižším startovním číslem předběhl. Napište program, který z těchto informací rekonstruuje pořadí, v němž šneci dobíhali do cíle.

Řešení

12-2-3 Jednosměrky (10 bodů)

Bylo jednou jedno království. A v onom království se začal rozmáhat motorismus. Silnice byly přecpány kočáry, trakaři i vozíky, křižovatky byly neprůjezdné. A tak se král rozhodl vylepšit nevábnou situaci v dopravě a poněkud zvýšit plynulost provozu. Rádce, jemuž byla realizace této velkolepé myšlenky svěřena, dostal nápad, že provoz by šlo bez větších nákladů zlepšit tak, že by se ze všech silnic udělaly jednosměrky. I najal si vás, abyste mu pro danou silniční síť zjistili, zda je možno ze silnic udělat jednosměrky tak, že se stále ještě půjde dostat z libovolného místa do libovolného (bez porušení předpisů samozřejmě). A pokud to možné je máte i vypsat, jak to učinit.

Váš program dostane na vstupu počet křižovatek N a počet silnic mezi křižovatkami M. Dále pak pro každou silnici dostane čísla dvou křižovatek, které spojuje (křižovatky jsou očíslovány od jedné do N). Na výstup má pak váš program buď vypsat, že ze silnic jednosměrky udělat nejde, nebo vypsat silniční síť s jednosměrkami – tedy seznam spojení křižovatek ve tvaru počáteční křižovatka → koncová křižovatka.

Příklad 1: Máme 4 města a 4 silnice – {1,2}, {3,2}, {3,4}, {1,4}. Silniční síť s jednosměrkami může vypadat třeba následovně: (2,3), (3,4), (4,1), (1,2).

Příklad 2: Máme 4 města a 4 silnice – {1,2}, {1,3}, {2,3}, {1,4}. Silniční síť s jednosměrkami neexistuje.

Řešení

12-2-4 Vysílače (11 bodů)

Společnost Shumm & Brumm se zabývá výstavbou sítí vysílačů. Protože signály z jednotlivých vysílačů se ruší, musí společnost zajistit, aby vysílače měly dostatečně malý výkon a k rušení tedy nedocházelo. Vývojové oddělení firmy po nákladném výzkumu zjistilo, že nejvíce se ruší nejbližší vysílače. Z toho poté již v relativně krátké době odvodilo, že pokud se nebudou rušit dva nejbližší vysílače, nebudou se rušit ani žádné dva jiné vysílače. Způsob, jak nalézt dva nejbližší vysílače, už ovšem oddělení nevyřešilo. A tak jste byli najati, abyste tento problém vyřešili vy.

Na vstupu tedy máte dány souřadnice N vysílačů a vaším úkolem je určit, které dva vysílače jsou nejblíže.

Příklad: Máme pět vysílačů o souřadnicích (0,0), (1,0), (-0.5,0), (0, 2), (1,1). Nejblíže jsou si vysílače jedna a tři.

Řešení

12-2-5 PRAM (11 bodů)

V minulém kole jste vymysleli, jak na PRAMu porovnávat dvě celá čísla zadaná po bitech. Než si řekneme úlohy druhého kola, přijměte prosím naši omluvu: Do vzorového příkladu pro CREW PRAM se nám vloudily dva překlepy – podmínka ukončení programu je samozřejmě lmem[4]<>0 a po ní následující řádek má správně být lmem[1]:=cpuid+lmem[3]. Doufáme, že jste uvedené překlepy snadno odhalili a opravili a že vás nijak neodradily od řešení našeho seriálu. A nyní již slíbená druhá úloha:

Vytvořte program, který jako vstup obdrží dvě posloupnosti délky n složené z nul a jedniček, které představují binární čísla (nejnižší bit je poslední). Délka posloupností je uložena v gmem[0], první posloupnost pak v gmem[1] až gmem[n], druhá v gmem[n+1] až gmem[2n]. Zápis čísel nemusí začínat jedničkou, např. první číslo může být 1100 a druhé 0110. Obsah paměťových buněk před začátkem výpočtu by pro tato dvě čísla tedy byl: 4,1,1,0,0,0,1,1,0.

Program tato dvě čísla sečte a výsledek uloží do paměťových buňek gmem[0] až gmem[n] tak, aby tyto obsahovaly jednotlivé cifry výsledného součtu ve formátu obdobném formátu vstupu programu; např. paměťová buňka gmem[0] obsahuje jedničku, pokud výsledný součet má n+1 cifer, jinak obsahuje 0. Obsah paměťových buněk po ukončení výpočtu by pro naše zadání měl tedy být: 1,0,0,1,0.

Úlohu postupně vyřešte pro EREW PRAM, CREW PRAM a P-CRCW PRAM.

Řešení