Zadání úloh školního kola 54. ročníku
Řešení každého příkladu musí obsahovat podrobný popis použitého algoritmu,
zdůvodnění jeho správnosti a diskusi o efektivitě zvoleného řešení (tzn.
posouzení časových a paměťových nároků programu).
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ů.
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.
Soutěžní úloha
Na vstupu dostanete počet zakázek, které Bořivoj na jeden konkrétní den obdržel. U každé zakázky
víte čas příchodu zákazníka a dobu, na jakou si chce pronajmout jednu pračku. Požadavky zákazníků
nejsou uvedeny v žádném konkrétním pořadí.
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.
Formát vstupu
První řádka textového souboru
pradelna.in obsahuje jediné přirozené číslo N<=10 000 - počet zákazníků. Dalších N řádek
obsahuje informace o jednotlivých zákaznících: na i-té z těchto řádek je uveden čas T
i,
kdy chce zákazník přijít, a doba T'
i, na kterou si chce pronajmout pračku.
Můžete předpokládat, že T
i a T'
i jsou celá čísla od 1 do 1 000 000 000.
Formát výstupu
První řádka textového souboru
pradelna.out obsahuje jediné číslo P - nejmenší možný počet praček,
s nimiž může Bořivoj obsloužit všechny zákazníky. Dalších N řádek bude obsahovat N čísel a
1 až a
N,
přičemž a
i je číslo pračky, kterou má použít i-tý zákazník. Předpokládejte, že pračky budou očíslovány
od 1 do P.
Příklad
Soubor
pradelna.in:
4
1000 1000
1900 900
1500 700
2000 500
Soubor
pradelna.out:
3
2
1
3
2
P-I-2 Závody
Letos se po několika letech opět konají slavné závody švábů. Závody probíhají
na pečlivě připravené překážkové dráze obsahující takové záludnosti, jako je
třeba mistička s cukrem. Švábí závodníci jsou na trať vypouštěni v minutových
intervalech a aby je bylo možno v cíli rozeznat, má každý závodník k sobě
připevněnu cedulku s minutou startu (první šváb má tedy číslo nula, druhý
jedna, atd.). Organizátory závodu by zajímalo, jak moc se švábi během
tréninkového běhu promíchali. Pokud by se totiž promíchali hodně, bylo by třeba
prodloužit intervaly mezi jednotlivými závodníky, aby se při běhu tolik neovlivňovali.
Jako míra promíchanosti závodníků byl stanoven počet dvojic závodníků, kteří
doběhli do cíle v opačném pořadí, než v jakém vyběhli na trať. Spočítat míru
promíchanosti pro dané pořadí švábů v cíli je již úloha pro vás.
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ů.
Formát vstupu
Vstupní textový soubor
zavody.in obsahuje dva řádky. Na prvním řádku je uvedeno
jedno celé číslo N, 1<=N<=30 000. Na druhém řádku je N různých
celých čísel z intervalu 0, ..., N-1 oddělených jednou mezerou.
Formát výstupu
Výstupní textový soubor
zavody.out obsahuje jediný řádek s jedním celým
číslem - počtem dvojic závodníků, kteří doběhli v opačném pořadí, než v jakém
vystartovali.
Příklad
Soubor
zavody.in:
5
1 0 4 2 3
Soubor
zavody.out:
3
P-I-3 Fylogenetika
Fylogenetika je obor biologie zabývající se rozpoznáváním vývojových vztahů mezi
organismy. Často používanou metodou je srovnávání genetického kódu. V této úloze
se budeme zabývat výrazně zjednodušenou variantou tohoto problému.
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.
Formát vstupu
Vstupní textový soubor
fylogen.in obsahuje několik řetězců složených z písmen `
A', `
C', `
G' a `
T',
reprezentujících genetické kódy jednotlivých organismů. Organismy jsou očíslovány
1, 2, ..., n; na i-tém řádku se nachází kód i-tého organismu. Můžete
předpokládat, že řetězců je nejvýše 50, každý z nich má nejvýše 50 znaků
a žádné dva řetězce nejsou stejné.
Formát výstupu
Výstupní textový soubor
fylogen.out tvoří seznam všech dvojic předek - potomek. Každá řádka výstupního souboru
popisuje jednu z těchto dvojic a sestává z čísla předka následovaného číslem potomka.
Dvojice mohou být uvedeny v libovolném pořadí, nesmějí se však opakovat.
Příklad
Soubor
fylogen.in:
ATAT
CATATG
CATATGA
CATATGG
Soubor
fylogen.out (jedno z možných správných řešení):
1 2
1 3
1 4
2 3
2 4
P-I-4 ALIK
Studijní text
Aritmeticko-logický integerový kalkulátor (zkráceně ALIK) je počítací stroj pracující
s W-bitovými celými čísly v rozsahu 0 až 2
W-1 včetně; kdykoliv budeme hovořit
o
číslech, půjde o tato čísla. Budeme je obvykle zapisovat ve dvojkové soustavě
polotučnými číslicemi a vždy si na začátek dvojkového zápisu doplníme příslušný počet nul,
aby číslic (bitů) bylo právě W. Většinou také nebudeme rozlišovat mezi číslem a
jeho dvojkovým zápisem, takže i-tým bitem čísla budeme rozumět i-tý bit jeho dvojkového
zápisu (bity číslujeme zprava doleva od 0 do W-1).
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 |
Pokud závorky neurčí jinak, vyhodnocují se operátory s vyšší prioritou před operátory
s nižší prioritou. V rámci stejné priority se pak vyhodnocuje zleva doprava (s výjimkou
operátoru
NOT , který je unární, a tudíž se musí vyhodnocovat zprava doleva).
Příklad 0 (jak fungují operátory; zde máme W=4)
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 |
Výpočet probíhá takto: Nejprve se do registru x nastaví vstup (to je vždy jedno číslo)
a do ostatních registrů nuly. Poté se provedou všechny příkazy v pořadí, v jakém jsou
v programu uvedeny, přičemž vždy se nejprve vyhodnotí
výraz na pravé straně a teprve
poté se jeho výsledek uloží do
registru, takže uvnitř výrazu je ještě možné pracovat
s původní hodnotou registru. Po dokončení posledního příkazu se hodnota v registru y
interpretuje jako výsledek výpočtu. Hodnoty v ostatních registrech mohou být libovolné.
Č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.
Příklad 1
Sestrojte program pro ALIK, který dostane na vstupu nenulové číslo a vrátí
výsledek 1 právě tehdy, je-li toto číslo mocninou dvojky, jinak vrátí nulu.
Řešení:
Nejdříve si všimněme, že mocniny dvojky jsou právě čísla, která
obsahují právě jeden jedničkový bit. Sledujme chování následujícího jednoduchého
programu.
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 |
Číslo v registru a se od x vždy liší tím, že nejpravější
1 se změní na
0 a všechny
0 vpravo od ní se změní na
1. Proto b=x
AND a se musí od x lišit právě přepsáním
nejpravější
1 na
0. (To proto, že bity vlevo od této
1 jsou stále stejné a A
AND A=A,
zatímco ve zbytku čísla se vždy
anduje
0 s
1, což dá nulu.) A jelikož mocniny dvojky
jsou právě čísla, v jejichž dvojkovém zápisu je právě jedna
1, spočte náš program
v b nulu právě tehdy, je-li x mocninou dvojky (nebo nulou, což jsme si ale zakázali).
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 |
Stačí tedy na konec našeho programu přidat
y := if(b,0,1) | y=0 nebo 1 |
a máme program, který rozpoznává mocniny dvojky v konstantním čase
a používá k tomu čísla o N+1 = O(N) bitech.
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 |
Příklad 2
Sestrojte program pro ALIK, který spočte
binární paritu vstupního čísla,
čili vrátí 0 nebo 1 podle toho, zda je v tomto čísle sudý nebo lichý počet jedničkových bitů.
Řešení:
Binární parita P(x) čísla x=x
N-1... x
1x
0 je podle definice rovna
x
0 XOR x
1 XOR ...
XOR x
N-1. Jelikož operace
XOR je
asociativní (A
XOR (B
XOR C) = (A
XOR B)
XOR C)
a komutativní (A
XOR B=B
XOR A), můžeme tento vztah
pro N=2
k (to opět můžeme bez újmy na obecnosti předpokládat) přeuspořádat na
P(x)=(x
0 XOR x
N/2)
XOR (x
1 XOR x
N/2+1)
XOR ...
XOR (x
N/2-1 XOR x
N-1),
což je ovšem parita čísla vzniklého vyxorováním horní a dolní poloviny čísla x.
Takže výpočet parity N-bitového čísla můžeme na konstantní počet příkazů
převést na výpočet parity N/2-bitového čísla, ten zase na výpočet parity
N/4-bitového čísla atd., až po log
2 N krocích
na paritu 1-bitového čísla, která je ovšem rovna číslu samému.
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) |
Náš programovací jazyk samozřejmě žádné celé části čísel
a podobné operace nemá, ale to vůbec nevadí, protože je vždy používáme jen
na podvýrazy závisící pouze na N, takže je v programu můžeme pro každé N
uvést jako konstanty. Například pro N=8 bude výpočet probíhat takto:
| 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 |
Soutěžní úlohy
- Sestrojte program pro ALIK, jehož výsledkem bude počet jedničkových bitů
ve dvojkovém zápisu čísla na vstupu.
- Sestrojte program pro ALIK, který k zadanému číslu x spočte nejbližší
větší číslo, v jehož dvojkovém zápisu je stejný počet jedniček jako v zápisu x. Pokud takové
číslo neexistuje, výsledek může být libovolný.