Na řešení úloh máte 4,5 hodiny čistého času.
Řešení každého příkladu musí obsahovat:
Hodnotí se nejen správnost programu, ale také kvalita popisu řešení a efektivita zvoleného algoritmu.
Na monitoru se zase jednou schyluje k velké bitvě mezi armádou hráče a armádou jeho počítače.
Každou armádu tvoří N příšer. Každou příšeru můžeme popsat dvěma přirozenými čísly: první popisuje její <útok> (útočnou sílu), druhé pak její <obranu> (obranné schopnosti). Příšeru s útokem a a obranou b budeme značit a/b.
Když spolu bojují dvě příšery a útok první je větší než obrana druhé, druhá příšera je zabita. Může se také stát, že se obě příšery zabijí navzájem nebo že obě přežijí. Příšera vyhraje souboj, pokud zabije druhou příšeru a sama přežije.
Příšery ovládané počítačem útočí, hráč se musí bránit. Proti každé z příšer počítače musí poslat právě jednu ze svých příšer. Všechny souboje probíhají současně.
vstup
3 9/2, 9/7, 8/8 100/100, 1/1, 7/8výstup
2(Nad příšerou 7/8 vyhraje jedině příšera 9/7. Příšeře 1/1 může hráč přiřadit kteroukoliv ze svých zbylých dvou příšer.)
vstup
4 10/1, 10/1, 10/2, 10/9 10/1, 10/1, 10/2, 10/8výstup
0(Bez ohledu na rozdělení se všechny příšery zabijí navzájem.)
vstup
4 7/3, 2/12, 47/47, 5/6 10/1, 4/7, 3/6, 1/1výstup
4(Jediné řešení: své příšery hráč přiřadí postupně třetí, první, druhé a čtvrté příšeře počítače.)
V Bürrolandu vyřešili otázku nezaměstnanosti po svém – zaměstnali hromadu úředníků. Aby měli noví úředníci co na práci, začali vydávat nejrůznější potvrzení, která je potřeba předkládat při různých příležitostech. A jelikož úředníků je mnoho, každý z nich je úzce specializovaný a vydává pouze jeden typ potvrzení. Jedno potvrzení ovšem může vydávat více úředníků.
Dostat od úředníka potvrzení, které vydává, není nikterak lehké. Abyste ho dostali, musíte mít potvrzení jiného konkrétního typu a k tomu ještě musíte úředníkovi předložit několik svých osobních dokladů. (Nezáleží na tom, jakých, důležitý je pouze jejich počet.)
Jožin už vlastní jedno potvrzení, ale potřeboval by si vyřídit potvrzení jiného typu. Nyní ho zajímá, jestli je to vůbec možné a pokud ano, jaký nejmenší počet osobních dokladů mu k tomu bude stačit. (Pro Jožina je snazší oběhat pár úředníků navíc než najít ve své rodné bažině rodný list.)
Typy potvrzení jsou očíslované od 1 do N. Jožin vlastní potvrzení typu 1 a shání potvrzení typu N.
Pro každého úředníka jsou dána tři čísla: typ potvrzení, které mu je potřeba ukázat, typ potvrzení, které vydává, a počet osobních dokladů, které je nutné mít s sebou (číslo od 0 do K).
Váš program má vypsat nejmenší počet osobních dokladů, které stačí k získání potvrzení typu N, a také pořadí, v jakém máme potvrzení vyřizovat. Pokud není možné požadované potvrzení získat, vypište místo toho zprávu, že to není možné.
vstup
N = 4, M = 5, K = 2 1 4 2 1 2 0 2 3 2 3 4 1 1 3 1výstup
1 3 4Existuje více způsobů, jak získat čtvrté potvrzení. Můžeme ho dostat přímo za potvrzení 1 (u prvního úředníka), ale k tomu potřebujeme dva doklady. Nebo si můžeme nejdříve zařídit potvrzení 2 (u druhého úředníka), potom 3 (u třetího) a nakonec 4 (u čtvrtého), ovšem k tomu potřebujeme předložit třetímu úředníkovi také 2 doklady. Nejlepší je získat potvrzení 3 (u pátého úředníka) a potom 4, na což nám stačí jediný doklad.
Mach a Šebestová spolu mají rozehranou partii piškvorek. Šebestová hraje s křížky a začínala.
V proměnných R a C je počet řádků a sloupců hrací plochy, v dvourozměrném poli A je na souřadnicích [i,j] (kde 0≤ i < R, 0≤ j < C) znak `X', `O' nebo `.' (zatím prázdné políčko). V proměnné K je délka řady potřebné k výhře partie.
Můžete předpokládat, že vstup korektně popisuje rozehranou partii, ve které je právě na tahu Šebestová. (Čili počet křížků a koleček je stejný a nikde na hrací ploše se ještě nevyskytuje K stejných znaků v řadě vedle sebe.)
vstup
R=6, C=5, K=4 A= ..... ..... ..... .OXO. .X... .....výstup
skončí úspěšně(Šebestová začne tahem na políčko [2,3], čili na políčko v třetím řádku a čtvrtém sloupci, čímž dostane tři znaky `X' vedle sebe. I když Mach odpoví tahem na políčko [5,0] nebo [1,4], Šebestová může v dalším tahu vždy táhnout na druhé z nich a vyhrát.)
vstup
R=6, C=5, K=4 A= XOXOX XOXOX OXO.O XO.OX X.... OXOXOvýstup
skončí neúspěšně(Šebestová prvním tahem řadu čtyř nevytvoří, dokonce ani nedokáže zabránit Machovi, aby příštím tahem vyhrál.)
vstup
R=5, C=6, K=6 A= ...... ...... ...... ...... ......výstup
skončí neúspěšně(Řada šesti se dá vytvořit jedině vodorovně. Mach proto snadno zabrání Šebestové vyhrát. Při optimální hře obou hráčů partie skončí remízou.)
Piškvorky jsou hra, kterou hrají dva hráči na čtverečkovaném papíru obdélníkového tvaru. Na začátku hry se hráči dohodnou na celém kladném čísle K. Každý hráč má svou značku: hráč, který začíná, obvykle používá křížek (`X'), druhý hráč kolečko (`O'). Hráči tahají střídavě, v každém tahu hráč zvolí prázdné políčko na hracím plánu a umístí na něj svou značku. Hra končí, pokud některý z hráčů kdekoliv na hracím plánu vytvořil souvislou řadu K svých znaků ve vodorovném, svislém nebo úhlopříčném směru. Pokud se celá plocha zaplní a nikdo nevyhrál, hra končí remízou.
(Tento studijní text je identický s textem uvedeným u úloh domácího i krajského kola.)
Za sedmero horami a sedmero řekami vymyslel vynálezce Kleofáš podivný stroj, který nazval paralelizátor. Na první pohled vypadal paralelizátor jako obyčejný počítač..\ Byl tu však jeden malý, ale o to důležitější rozdíl. Za určitých okolností dokázal paralelizátor paralelně (tj. současně) spustit více větví programu, aniž by ho to jakkoliv zpomalilo. Kleofáš rychle pochopil, že jen ze slovního popisu tohoto zázraku by nikdo nebyl moc moudrý, a tak vymyslel i programovací jazyk, v němž je možné psát programy pro jeho paralelizátor.
Programy pro paralelizátor se budou od klasických lišit mimo jiné tím, že nebudou mít žádný výstup. Budeme pouze rozlišovat, zda program skončil úspěšně nebo neúspěšně. U klasických programů by to znamenalo, že nás zajímá jen tzv. exit code (návratová hodnota) programu.
Kleofášův programovací jazyk je téměř přesnou kopií jazyka Pascal. Oproti klasickému Pascalu v něm nemáme k dispozici generátor náhodných čísel (a tedy například funkci random), takže je předem dáno, jak bude výpočet každého programu vypadat. Zato přibyly čtyři nové příkazy: Accept, Reject, Both(x) a Some(x) (kde x je proměnná typu integer).
Příkaz Accept úspěšně ukončí běžící program.
Příkaz Reject ukončí běžící program, ale neúspěšně. Stejný význam má i provedení standardního Pascalského příkazu Halt a ukončení výpočtu programu přechodem přes koncové End., příkaz Reject definujeme jen kvůli názornosti.
V následujícím textu budeme vytvořením kopie programu rozumět to, že se v operační paměti vytvoří úplně přesná kopie celého programu včetně obsahu jeho proměnných – výsledek bude stejný, jako kdybychom už od začátku daný program spustili ne jednou, ale dvakrát.
Příkaz Both(x) zastaví aktuálně běžící program. Vytvoří se dvě jeho identické kopie. V první z nich je hodnota proměnné x nastavena na 0, v druhé na 1. Obě kopie programu jsou paralelně spuštěny, přičemž jejich výpočet pokračuje příkazem následujícím za příslušným příkazem Both.
Pokud obě kopie úspěšně skončí, v následujícím taktu procesoru úspěšně skončí i původní program. Jestliže jedna z kopií skončí neúspěšně (druhá přitom skončit ani nemusí), původní program v následujícím taktu skončí také neúspěšně. Ve všech ostatních případech (tj. když jedna kopie nikdy neskončí a druhá buď rovněž nikdy neskončí, nebo skončí úspěšně) původní program nikdy neskončí.
Příkaz Some(x) funguje podobně. Rovněž zastaví aktuálně běžící program. Opět se vytvoří dvě jeho identické kopie, v první z nich je hodnota proměnné x nastavena na 0, v druhé na 1. Obě kopie programu jsou paralelně spuštěny, přičemž jejich výpočet pokračuje příkazem následujícím za příslušným příkazem Some.
Jakmile některá z kopií úspěšně skončí, v následujícím taktu procesoru úspěšně skončí i původní program. Pokud obě
kopie skončí neúspěšně, v následujícím taktu procesoru skončí neúspěšně také původní program. Ve všech ostatních případech (tj. když jedna kopie nikdy neskončí a druhá buď rovněž nikdy neskončí, nebo skončí neúspěšně) původní program nikdy neskončí.
Slovně můžeme tyto operace popsat následovně: Příkaz Both provádí „paralelní and” – ověří, zda obě větve úspěšně skončí. Příkaz Some provádí „paralelní or” – ověří, zda aspoň jedna z větví úspěšně skončí.
Netrvalo dlouho a Kleofáš si uvědomil, že na takovémto zázračném zařízení dokáže některé problémy řešit až neuvěřitelně rychle. Například testování prvočíselnosti je skutečně snadné.
{ VSTUP: N : integer; }
var moc2, pocet_cifer : integer;
cislo : integer;
i,x : integer;
begin
{ ošetříme okrajový případ }
if N = 1 then Reject;
{ zjistíme, kolik má N cifer ve dvojkové soustavě }
moc2 := 1;
pocet_cifer := 0;
while moc2 < N do begin
moc2 := moc2 * 2;
inc(pocet_cifer);
end;
{ vygenerujeme čísla od 0 do 2^pocet_cifer - 1 }
cislo := 0;
for i:=1 to pocet_cifer do begin
Both(x);
cislo := 2*cislo + x;
end;
{ moc malé dělitele zkoušet nebudeme, prohlásíme za dobré }
if cislo <= 1 then Accept;
{ ani příliš velké dělitele zkoušet nebudeme }
if cislo >= N then Accept;
{ jinak zkoušíme, zda vygenerované číslo dělí N }
if N mod cislo <> 0 then Accept;
Reject;
end.
Názorně si ukážeme, jak vypadá výpočet paralelizátoru na tomto programu pro N=3 a pro N=6. Kopie programu, které vznikají během výpočtu, budeme číslovat v pořadí, v jakém vznikají.
Pro N=3 bude výpočet probíhat následovně:
Pro N=6 bude výpočet probíhat následovně:
Pomocí volání příkazu Some paralelně projdeme všechna čísla m∈ M, stačí nám, když libovolné jedno z nich dělí N.
(Jiný pohled na totéž řešení: Pomocí volání příkazu Some „uhodneme” dělitele m∈ M a ověříme, zda jsme ho uhodli správně. Na náš program se můžeme dívat tak, že se nevětví, ale každé volání Some „uhodne” a do x dosadí „správnou” hodnotu. Jestliže tedy N má v množině M dělitele, najdeme ho, jinak skončíme s nějakým číslem, které N nedělí.)
Časová složitost programu je O(K).
{ VSTUP: N, K : integer; }
var cislo : integer;
i,x : integer;
begin
{ paralelně zkoušíme čísla od 0 do 2^K - 1 }
cislo := 0;
for i:=1 to K do begin
Some(x);
cislo := 2*cislo + x;
end;
{ 0 a 1 do množiny M nepatří }
if cislo <= 1 then Reject;
{ zkusíme, zda vygenerované číslo dělí N }
if N mod cislo = 0 then Accept;
Reject;
end.