V úlohách P-I-1, P-I-2 a P-I-3 je třeba k řešení připojit odladěný program zapsaný v jazyce Pascal, C nebo C++. Program se odevzdává v písemné formě (jeho výpis je tedy součástí řešení) i na disketě, aby bylo možné otestovat jeho funkčnost. Slovní popis řešení musí být ovšem jasný a srozumitelný, aniž by bylo nutno nahlédnout do zdrojového textu programu. V úloze P-I-4 je nutnou součástí řešení program pro paralelizátor.
Řešení úloh domácího kola MO kategorie P vypracujte a odevzdejte nejpozději do 15.11.2005. Vzorová řešení úloh naleznete po tomto datu na Internetu na adrese http://mo.mff.cuni.cz. Na stejném místě jsou stále k dispozici veškeré aktuální informace o soutěži a také archív soutěžních úloh a výsledků z minulých ročníků.
P-I-1 Pluky
Na monitoru se právě schyluje k velké bitvě mezi armádou hráče a armádou jeho počítače. Síly jsou vyrovnané, obě armády
mají stejný počet pluků, ovšem jednotlivé pluky mohou být tvořeny různým počtem vojáků. Na začátku bitvy se pluky obou
armád seřadí do dvou řad tak, že proti každému hráčovu pluku stojí právě jeden pluk patřící počítači. Potom začne
vlastní boj. Pluky stojící proti sobě na sebe zaútočí. A protože v množství je síla, zvítězí ten z nich, který má více
vojáků. Pokud náhodou mají soupeřící pluky stejný počet vojáků, vyhraje pluk patřící počítači.
Hráčova armáda má schopné špióny, kteří před bitvou zjistili, kolik vojáků má nepřítel v kterém pluku a jak jsou jeho pluky rozmístěny. Vaším úkolem je rozmístit na základě těchto informací hráčovy pluky tak, aby co nejvíce z nich svůj souboj vyhrálo.
pluky.in 5 7 12 1 7 47 7 12 1 7 47
pluky.out 3(Pokud hráč rozmístí své pluky správně, zvítězí jeho pluky velikosti 47, 12 a jeden z pluků velikosti 7.)
pluky.in 4 10 10 10 10 10 10 10 10
pluky.out 0(Při jakémkoliv rozestavení všechny pluky hráče prohrají.)
pluky.in 5 1 3 5 7 9 2 4 6 8 10
pluky.out 4(Hráč obětuje svůj nejmenší pluk, pošle ho proti pluku velikosti 10. Ostatní pluky potom lze rozmístit tak, aby vyhrály.)
teleport.in 3 4 1 2 5 2 3 -7 1 3 -1 1 3 16
teleport.out -2(Prvním teleportem se vědci dostanou do lokality 2 v čase 5, odtud druhým do lokality 3 v čase 5+(-7)=-2. Ostatní možnosti jsou horší.)
teleport.in 2 2 1 1 -1 1 2 0
teleport.out Vedci poznaji vznik vesmiru(Dříve než se vědci druhým teleportem přesunou do bufetu, mohou prvním odcestovat libovolně daleko do minulosti.)
teleport.in 4 3 1 2 -1 2 3 0 4 3 10
teleport.out Vedci umrou hlady(Poslední teleport nemohou vědci použít na přesun z lokality 3 do lokality 4, jedině naopak.)
Na stará kolena krále navštívila teta Paranoia a našeptala mu, že sousedé chtějí napadnout jeho království. Proto se král rozhodl, že lakota musí jít stranou a že postaví ve městech vojenské posádky. Paranoia však šeptala dál: „Zbláznil ses? Když budou dvě posádky v sousedních městech, budou si mezi sebou posílat zprávy. A víš, jak to dopadne... Nech hodně vojáků pohromadě a vzbouří se proti tobě!”
Tři dny a tři noci král nespal, až vymyslel následující kompromis: Vybere několik měst, v nichž postaví vojenské posádky. Aby mu nehrozila vzpoura, rozhodl se, že nikdy nesmějí být pohromadě více než tři posádky. Teď sedí nad mapou a vymýšlí, jak je má jenom rozmístit, aby království bylo co nejlépe zabezpečeno.
Na vstupu máte zadán počet měst N a popis cest mezi nimi. Cest je právě N-1, nikde se nekřižují, jimi tvořená síť je souvislá a spojuje všechna města. Pro každé město i známe číslo bi — toto číslo udává, kolik přidá vojenská posádka v i-tém městě k bezpečnosti království. Královým (a vaším) úkolem je vybrat množinu měst, v nichž budou umístěny posádky. Tato množina musí splňovat následující podmínky:
Poslední řádek vstupního souboru obsahuje N celých čísel b1,...,bN (0 ≤ bi ≤ 10,000), která udávají, kde je jak výhodné umístit vojenskou posádku.
posadky.in 7 1 2 2 3 3 4 4 5 5 6 6 7 1 1 1 1 1 1 1
posadky.out 6 1 2 3 5 6 7(Všude je zisk z posádky stejný, chceme jich umístit co nejvíce.)
posadky.in 5 1 5 2 5 3 5 4 5 1 6 5 2 1000
posadky.out 1011 2 3 5(Zjevně chceme mít posádku ve městě 5. Potom už ale můžeme vybrat jen dvě z ostatních měst.)
posadky.in 5 1 5 2 5 3 5 4 5 4 4 4 4 5
posadky.out 16 1 2 3 4(Ne vždy se vyplatí vybrat město s nejvyšší hodnotou bi.)
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ě:
(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.
b)
Nad polem přirozených čísel můžeme postavit „pyramidu”. Spodní řádek pyramidy bude tvořit samotné pole. Každý vyšší
řádek bude o 1 kratší než předcházející, přičemž i-tý prvek v novém řádku je roven součtu i-tého a (i+1)-tého
prvku z řádku pod ním, modulo 10,000 (tzn. pokud by součet vyšel větší než 9,999, necháme z něho v pyramidě jen jeho
poslední čtyři cifry). Vrchní řádek pyramidy je tvořen jediným číslem.
V proměnné N máme přirozené číslo. V poli A na pozicích 1 až N máme N přirozených čísel menších než 10,000. V proměnné V je nezáporné celé číslo menší než 10,000.
Napište co nejrychlejší program pro paralelizátor, který pro každý vstup skončí, přičemž úspěšně skončí právě tehdy, když hodnota V je na vrcholu pyramidy postavené nad polem A.
Vstup: N=4 A=( 6, 3, 9, 3 ) V=17
Výstup: skončí neúspěšně(Pyramida vypadá následovně:)
45 21 24 9 12 12 6 3 9 3
Vstup: N=4 A=( 1, 2, 3, 4 ) V=20
Výstup: skončí úspěšně(Pyramida vypadá následovně:)
20 8 12 3 5 7 1 2 3 4