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

Zadání úloh

11-2-1 Kva-kva-kvadrant (11 bodů)

Již z minulé série všichni znáte princip kvadrantových kódů obrázků. Pro ty s pamětí zvíci řešeta připomínáme: Obrázky nakreslené do čtvercové sítě velikosti 2n ×2n se kódují kvadrantovými kódy takto:

Vaším úkolem tentokráte je napsat program, který si přečte posloupnost transformací (potenciálně velmi dlouhý řetězec znaků, z nichž každý odpovídá jedné transformaci), a poté bude ze vstupu číst jednotlivé zakódované obrázky Zi a na každý z nich odpoví kódem obrázku vzniklého postupným aplikováním všech zadaných transformací v zadaném pořadí na Zi.

V řetězci se mohou vyskytovat tyto transformace:

Příklad: Posloupnost transformací -XI+YI převede obrázek s kódem 22000120010201011 na tentýž obrázek.

Řešení

11-2-2 Zákeřná posloupnost (9 bodů)

Na vstupu dostanete dloooouhatánskou posloupnost přirozených čísel, ve které je každé číslo dvakrát … až na jedno darebné, jež je tam pouze jednou. A jak přijít na to, které to je?

Řešení

11-2-3 Případ scottského skota (10 bodů)

Sir Walter Scott byl archeolog amatér. Původním povoláním skotačící pasáček šlechtěného skotu (pochopitelně narozený v Oxfordu), nyní ovšem skotský šlechtic (na tom má zásluhu zejména to, že při svém amatérském archeologování vykopal něco jam a v nich učinil pár epochálních objevů – mimo jiné našel zlatou minci z doby železné, několik trilobajtů a blíže neurčené množství zakopaných psů). A sir Scott je hrozně bohatý. A ještě víc lakomý.

Jednoho dne náš skot Skot Scott objevil na dně jedné bezedné jámy plánek dosud neobjeveného bludiště, a tak začal okamžitě plánovat, jak bludištěm projít až k pokladu, který v něm jistě bude skryt (že v bludištích bývají poklady, to ví přeci každý). Tedy ne, že by se začal shánět po tom, kde vlastně bludiště je – on si totiž ponejprv všiml, že některé chodby jsou přehrazeny dveřmi, od kterých mu jistě nikdo nedá klič, a proto se s lakotností sobě vlastní jal vymýšlet, jak bludištěm projít, dveře "odemykat" krumpáčem a přitom si krumpáč co nejméně otlouci, aby si nemusel ještě léta kupovat nový.

Úloha: Na vstupu je plánek bludiště (čtvercová matice velikosti N×N, v každém políčku je buďto 0 (místnost), 1 (zeď), 2 (prokopnutelné dveře), 3 (poklad, vyskytuje se pouze jednou) nebo 4 (místnost, kde začínáte; rovněž unikátní). Vaším cílem je najít cestu (to jest posloupnost políček sousedících hranou [nikoliv pouze rohem]) začínající na políčku typu 4, končící políčkem typu 3, neobsahující políčko typu 1 a k tomu ještě takovou, která prochází nejmenším počtem políček typu 2. Pokud je takových cest více, vyberte libovolnou z nejkratších.

Řešení

11-2-4 Alea iacta est (10 bodů)

V rovině je dána souřadná soustava (tak, jak už to býva – dvě na sebe kolmé souřadné osy, ta první svislá, ta druhá vodorovná, na obou stejně velké dílky), a v souřadné soustavě n bodů (jak už to bývá – svými souřadnicemi) a výchozí místo M. Vaším úkolem je vymyslet program pro rozmisťovacího robota takový, aby začal v bodě M (počáteční směr pohybu si můžete zvolit), do každého z daných n bodů umístil kostičku (a nikam jinam!) a skončil opět v bodě M. Krásně jednoduché, že?

Robota ovšem zkonstruovala nejmenovaná firma nejmenovaného počítačového magnáta proslulá jednak nejmenovaným "operačním systémem" a jednak tím, že se snaží ovládání všeho zjednodušovat. Robot má díky tomu velice jednoduchý programovací jazyk sestávající z příkazů G(a) (jdi dopředu o a jednotek), L (umísti kostičku a otoč se o 90° doleva), R (umísti kostičku a otoč se o 90° doprava). Takže zase tak jednoduché to přeci jen nebude, že?

Úloha: Napište program, který dostane na vstupu souřadnice všech n požadovaných kostiček a počátečního (či koncového, jak chcete) bodu M a jeho výstupem bude program pro umisťovacího robota takový, aby robot splnil svůj úkol, případně zpráva o tom, že to nelze.

Řešení

11-2-5 Mnoho CPŮ, složitosti smrt (12 bodů)

Minule jsme si zavedli nedeterministický programovací jazyk, tentokráte pro změnu zkusíme programovat deterministicky, zato však paralelně – představte si, že máte počítač, který umí provádět tolik programů najednou, kolik si řeknete. Takový paralelní počítač budeme programovat opět v trošku modifikovaném klasickém programovacím jazyku (řekněme Pascalu či Céčku); zato však zavedeme vedle normálních bloků (begin … end či { … }) ještě bloky, před něž budeme psát klíčové slovo parallel, což bude znamenat, že všechny příkazy takového bloku se budou provádět najednou (nesmějí ovšem zapisovat do těchže proměnných či jedna větev výpočtu do jedné proměnné zapisovat a druhá z ní číst). Dobu potřebnou k vykonání takového paralelního bloku stanovíme jednoduše jako maximum z časů provádění jednotlivých příkazů (pozor, mohou zahrnovat i volání funkcí!).

Příklad: Tento program v P-Pascalu (paralelním Pascalu) počítá najednou minimum a maximum ze zadaných čísel:

var x,n,min,max:integer;
begin
   read(n);
   min:=-maxint; max:=maxint;
   while n>0 do begin
      read(x);
      parallel begin
         if x<min then min:=x;
         if x>max then max:=x;
         n:=n-1;
      end;
   end;
   writeln(min, max);
end.

Úlohy:

  1. Napište paralelní funkci, která nalezne nejmenší prvek v daném poli v čase rychlejším než O(N).
  2. Dokažte, že vše, co se dá spočítat na paralelním počítači, lze spočítat i na počítači klasickém (sekvenčním), možná ovšem daleko, daleko pomaleji.
  3. Dokažte, že cokoliv, co šlo naprogramovat na nedeterministickém počítači v čase omezeném nějakým polynomem, lze v polynomem omezeném čase (možná však jiným polynomem než tím předešlým) spočítat na počítači paralelním.

Řešení