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 zapište navržený algoritmus ve formě programu v jazyce ALIK.
Řešení úloh domácího kola MO kategorie P vypracujte a odevzdejte nejpozději do 15.11.2004. 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 Prádelna
Bořivoj se rozhodl, že začne podnikat - a to ve velkém. Jednou v noci, poté co upadl v koupelně,
dostal skvělý nápad: otevře si prádelnu. Každý, kdo přijde, si bude moci za malý obnos půjčit
pračku, pokud bude nějaká volná, a vypere si své prádlo.
Ihned se tedy zeptal svých přátel, zda by chtěli jeho prádelnu navštěvovat, a zjistil, že
zájem je opravdu veliký. Brzy ani nevěděl, kolik praček bude vůbec potřebovat, aby se dostalo
na všechny zákazníky. A proto se rozhodl obrátit se na vás s prosbou o pomoc.
Vaším úkolem je zjistit, kolik nejméně praček bude Bořivoj potřebovat, aby si každý zákazník mohl pronajmout pračku na celou požadovanou dobu od svého příchodu. Kromě minimálního počtu praček musíte pro Bořivoje vytvořit ještě seznam, podle kterého bude posílat zákazníky k volným pračkám.
Váš program dostane na vstupu počet švábů N a pořadí, v jakém švábi doběhli do cíle (tedy nějakou permutaci čísel 0,...,N-1). Na výstup má váš program vypsat míru promíchanosti závodníků.
Genetický kód budeme mít uložen jako řetězec skládající se z písmen `A', `C', `G' a `T'. Budeme předpokládat, že vývoj nového druhu probíhá tak, že se na začátek nebo na konec genetického kódu připojí nové geny - to je samozřejmě pouze idealizace (čti: úplný nesmysl). Dostanete zadán genetický kód několika organismů, vaším úkolem je nalézt mezi nimi všechny dvojice předek - potomek, tj. takové, že genetický kód předka je souvislým podřetězcem genetického kódu potomka.
Paměť stroje je tvořena 26 registry pojmenovanými a až z. Každý registr vždy obsahuje jedno číslo.
ALIK se řídí programem, což je posloupnost přiřazovacích příkazů typu registr:=výraz, přičemž výraz může obsahovat konstanty (čísla zapsaná ve dvojkové soustavě), registry, závorky a následující operátory (velká písmena značí podvýrazy, v pravém sloupci jsou priority operátorů):
| A + B | sečte čísla A a B. Pokud je výsledek větší než 2W-1, číslice vyšších řádů odřízne. Jinými slovy, počítá součet modulo 2W. | 4 |
| A - B | odečte od čísla A číslo B. Pokud je A < B, spočte 2W + A - B, čili rozdíl modulo 2W. | 4 |
| NOT A | spočte bitovou negaci čísla A, což je číslo, jehož i-tý bit je 0 právě tehdy, je-li i-tý bit čísla A roven 1, a naopak. | 9 |
| A AND B | bitové operace: | 8 |
| A OR B | Vyhodnocují se tak, že se i-tý bit výsledku spočte z i-tého bitu čísla A a | 7 |
| A XOR B | i-tého bitu čísla B podle následujících tabulek: | 7 |
| 0 AND 0 = 0 0 OR 0 = 0 0 XOR 0 = 0 | ||
| 0 AND 1 = 0 0 OR 1 = 1 0 XOR 1 = 1 | ||
| 1 AND 0 = 0 1 OR 0 = 1 1 XOR 0 = 1 | ||
| 1 AND 1 = 1 1 OR 1 = 1 1 XOR 1 = 0 | ||
| A << B | posune číslo A o B bitů doleva, čili doplní na jeho konec B nul a odřízne prvních B bitů, aby byl výsledek opět W-bitový. | 2 |
| A >> B | posune číslo A o B bitů doprava, čili doplní na jeho začátek B nul a odřízne posledních B bitů, aby byl výsledek opět W-bitový. | 2 |
| a+b AND c+d = (a+(b AND c))+d | zde zafungují priority operátorů |
| 0101 + 1110 = 0011 | nejvyšší bit výsledku 10011 se již oříznul |
| 0001 - 1111 = 0010 | odčítáme modulo 16=10000 |
| 0101 AND 0011 = 0001 | takto funguje and |
| 0101 OR 0011 = 0111 | takto or |
| 0101 XOR 0011 = 0110 | a takto xor |
| (1 << 11) - 1 = 1000 - 1 = 0111 | jak vyrobit pomocí << posloupnost jedniček |
| a OR NOT a = 1111 | jak získat z čehokoliv samé jedničky |
Často budeme potřebovat, aby program mohl pracovat s většími čísly, než je číslo na vstupu, takže budeme rozlišovat velikost vstupu N (tj. počet bitů potřebných k zapisu vstupní hodnoty) a velikost W registrů a mezivýsledků, kterou si při psaní programu sami určíme. Pokud bychom ovšem povolili exponenciálně velká čísla (tedy W=2N), mohli bychom cokoliv spočíst v konstantním čase - stačilo by do jedné dlouhatánské konstanty uvedené v programu zakódovat všechny možné výsledky programu pro všechny hodnoty vstupu. Tak dlouhé registry lze však stěží považovat za realistické, proto přijměme omezení, že W musí být polynomiální ve velikosti vstupu, čili že existuje konstanta k taková, že pro každé N je W <= Nk.
Ne vždy si ovšem vystačíme s jedním programem, který funguje pro všechny velikosti vstupu - mnohdy potřebujeme podle N měnit hodnoty pomocných konstant v programu, někdy také nějakou operaci opakovat vícekrát v závislosti na velikosti vstupu. Povolíme si tedy programy zapisovat obecněji, a to tak, že uvedeme seznam pravidel, jež nám pro každé N vytvoří program, který počítá správně pro všechny vstupy velikosti N. [Formálně bychom tato pravidla mohli zavést třeba jako programy v nějakém klasickém programovacím jazyce. My si ale formalismus odpustíme a budeme je popisovat slovně.]
Při řešení úloh budeme chtít, aby časová složitost vygenerovaných programů, tedy jejich délka v závislosti na N, byla co nejmenší. Mezi stejně rychlými programy je pak lepší ten, který si vystačí s kratšími čísly, čili s menším W (to je analogie prostorové složitosti). Podobně jako u klasických programů ovšem budeme v obou případech přehlížet multiplikativní konstanty.
Zmiňme ale ještě konvence, které budeme používat při psaní všech ukázkových programů:
V levém sloupci naleznete jednotlivé příkazy, v pravém sloupci obecný tvar
spočítané hodnoty pro libovolné N. Pokud se nějaká číslice
nebo skupina číslic opakuje vícekrát, značíme opakování exponentem, tedy
08 je osm nul, (01)3 je zkratka za 010101. Velkými písmeny značíme
blíže neurčené skupiny bitů.
| x=A10i | |
| a := x-1 | a=A01i |
| b := x AND a | b=A00i |
Zbývá tedy vyřešit, jak z nuly udělat požadovanou jedničku a z nenuly nulu. K tomu si zavedeme operaci r := if(s,t,u), která bude realizovat podmínku: pokud s<>0, přiřadí r:=t, jinak r:=u. Provedeme to jednoduchým trikem: rozšíříme si registry o jeden pomocný bit vlevo, nastavíme v r tento bit na jedničku a sledujeme, zda se zmenšením vzniklého čísla o jedničku tento bit změní na nulu nebo ne:
| v := s OR 10N | v=1 s |
| v := v - 1 | v=1r' (je-li r<>0), jinak 01N |
| v := v AND 10N | v=10N nebo 00N |
| v := v >> N | v=0N1 nebo 0N0 |
| v := v - 1 | v=0N+1 nebo 1N+1 |
| r := (u AND v) OR (t AND NOT v) | r=t nebo u |
| y := if(b,0,1) | y=0 nebo 1 |
Ještě si ukažme, jak bude probíhat výpočet pro dva konkrétní 8-bitové vstupy (tehdy je N=8 a W=9):
| x=001011000 x=000100000 | |
| a := x-1 | a=001010111 a=000011111 |
| b := x AND a | b=001010000 b=000000000 |
| v := b OR 100000000 | v=101010000 v=100000000 |
| v := v - 1 | v=101001111 v=011111111 |
| v := v AND 100000000 | v=100000000 v=000000000 |
| v := v >> 8 | v=000000001 v=000000000 |
| v := v - 1 | v=000000000 v=111111111 |
| y := (000000001 AND v) OR (000000000 AND NOT v) | y=000000000 y=000000001 |
Paritu tedy vypočteme na logaritmický počet příkazů pracujících s N-bitovými čísly takto:
| p := x >> N/2 | p=horních N/2 bitů x |
| q := x AND 1N/2 | q=dolních N/2 bitů x |
| x := p XOR q | x=N/2-bitové číslo s paritou jako původní x |
| x := (x >> N/4 ) XOR (x AND 1N/4) | x=N/4-bitové ... (můžeme psát zkráceně) |
| ... | |
| x := (x >> 1) XOR (x AND 1) | x=1-bitové ... |
| y := x | y=x (už jen zkopírovat výsledek) |
| x=00110110 | |
| p := x >> 4 | p=99990011 |
| q := x AND 1111 | q=99990110 |
| x := p XOR q | x=99990101 |
| x := (x >> 2) XOR (x AND 11) | x=99999900 |
| x := (x >> 1) XOR (x AND 1) | x=99999990 |
| y := x | y=00000000 |