Matematická olympiáda – kategorie P

Zadání úloh krajského kola 54. ročníku

Krajské kolo

Krajské kolo 54. ročníku MO kategorie P se konalo v úterý 11. 1. 2005 v dopoledních hodinách. Na řešení úloh bylo 4 hodiny čistého času. V krajském kole MO-P se neřeší žádná praktická úloha, pro zajištění rovných podmínek řešitelů ve všech krajích je použití počítačů při soutěži zakázáno.

Ř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.

P-II-1 Prádelní salón

Z Bořivoje se stal díky vaší pomoci úspěšný podnikatel a jeho klientela zahrnuje i bohatší a malichernější zákazníky. Pokud totiž nějaký zákazník uvidí dva různé zákazníky používat stejnou pračku, nebude už tuto prádelnu dále navštěvovat: „No považte, přece nelze prát prádlo s lidmi, kteří nemají na to, aby si zaplatili pračku sami pro sebe!”

Soutěžní úloha

Na vstupu dostanete N <= 10 000 – počet zákazníků, kteří navštíví Bořivojovu prádelnu během jednoho dne. U každého zákazníka je zadán čas jeho příchodu a doba, na jakou si chce pronajmout pračku (obojí jsou celá čísla mezi 1 a 1 000 000 000). 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 Bořivoj potřebuje, aby všichni jeho zákazníci byli zcela spokojeni. Zákazník bude spokojen, pokud si bude moci pronajmout pračku od okamžiku příchodu na dobu, kterou požaduje (je samozřejmé, že jednu pračku nemohou používat dva různí zákazníci současně), a navíc během doby, kdy bude prát, nebude žádnou pračku využívat více zákazníků po sobě. Kromě určení 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.

Příklad:


Pro 5 zákazníků, jejichž příchody a doby praní jsou

  1000 1000
  3000 2000
  4500 500
  1500 500
  2000 2000

jsou potřeba alespoň 3 pračky a přiřazení praček zákazníkům například takové:

  zákazník 1 bude u pračky 2
  zákazník 2 bude u pračky 3
  zákazník 3 bude u pračky 1
  zákazník 4 bude u pračky 3
  zákazník 5 bude u pračky 2

Všimněte si, že zákazníci 3 a 5 nemohou dostat stejnou pračku, protože by je viděl zákazník 2 pracovat u stejné pračky.

P-II-2 Zakázané rozdíly

Mějme dáno celé kladné číslo N, N≥2, a soustavu podmínek tvaru xi-xj≠ai,j, kde x1, ..., xN+1 jsou proměnné, ai,j jsou celá čísla mezi 0 a N-1 a pro každou dvojici indexů i a j, 1≤i<j≤N+1 soustava obsahuje právě jednu podmínku. Soustavu budeme řešit modulo modulo zadané číslo N, tj. všechny aritmetické operace jsou prováděny modulo N. Připomeňme si, že výsledkem aritmetické operace provedené modulo N je zbytek po dělení původního výsledku číslem N, např. (2+3)%4=1, (2-3)%4=3, (3*2)%5=1, (3*4)%6=0, atd. Všimněte si zejména způsobu počítání, pokud je původní výsledek operace záporný. Nalezněte algoritmus, který pro zadané N a čísla ai,j zjistí, zda zadaná soustava podmínek má řešení, tzn. zda existují čísla x1,...,xN+1∈{0,...,N-1} taková, že rozdíl xj-xi-ai,j není dělitelný N pro žádné i a j, 1≤i<j≤N+1. Pokud má soustava řešení, algoritmus musí také libovolné její řešení nalézt a vypsat.

Příklad 1:

Pro N=3, máme zadány následující podmínky:
x1 - x2 ≠ 1
x1 - x3 ≠ 2
x1 - x4 ≠ 2
x2 - x3 ≠ 2
x2 - x4 ≠ 1
x3 - x4 ≠ 0

Soustava má řešení, např. x1=x2=x4=2 a x3=1.

Příklad 2:

Pro N=2, máme zadány následující podmínky:
x1 - x2 ≠ 1
x1 - x3 ≠ 0
x2 - x3 ≠ 1

Pokud x1=0, pak x2=0 podle první podmínky a x3=1 podle druhé podmínky. Potom ale třetí podmínka není splněna. Podobně pokud x1=1, x2 musí být rovno 0 a x3 rovno 1 a třetí podmínka opět není splněna. Zadaná soustava podmínek tedy nemá řešení.

P-II-3 Redundantní redundance

Úřad pro potírání redundantních repetic (zřízený Komisí pro likvidaci redundantních úřadů) se zabývá odstraňováním zbytečně opakovaných dokumentů v archivech. Procházení archivů je samozřejmě velmi nudná práce, která odvádí úředníky od jiných, mnohem zajímavějších a jistě i prospěšnějších využití jejich pracovního času. Velmi by je proto potěšilo, kdybyste pro ně napsali program řešící následující úlohu: Je dáno přirozené číslo k a nějaký znakový řetězec T. Určete souvislý podřetězec délky k, který se v T nejvíce opakuje, a také počet jeho výskytů R. Jednotlivé výskyty tohoto řetězce se mohou částečně překrývat. V případě, že existuje více řetězců, které se opakují R-krát, vypište jeden libovolný z nich.

Příklad:

Pro vstup abababa a k=3 je nejčastějším řetězcem aba opakující se 3-krát.

P-II-4 ALÍK

Definici stroje ALIK naleznete ve studijním textu za touto úlohou. Od domácího kola se liší tím, že přibyly operace násobení, dělení a zbytku po dělení a Příklad 3 na tyto operace.

Soutěžní úloha

Sestrojte program pro ALIK, který k zadanému číslu x=xN-1... x1x0 nalezne zrcadlové číslo y=x0x1... xN-1, tj. číslo, jehož dvojkový zápis vznikne zapsáním N-bitového dvojkového zápisu čísla x (včetně případných počátečních nul) pozpátku.

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ž 2W-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 + Bseč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 - Bodečte od čísla A číslo B. Pokud je A < B, spočte 2W + A - B, čili rozdíl modulo 2W.4
A * Bvynásobí dvě čísla, výsledek opět modulo 2W.6
A / Bvydělí číslo A číslem B dělení nulou dá vždy výsledek 0.6
A % Bvrátí zbytek po dělení čísla A číslem B, čili A - A*(A % B) pokud je B=0, je výsledek roven A.6
NOT Aspoč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 Bbitové operace:
A OR BVyhodnocují se tak, že se i-tý bit výsledku spočte z i-tého bitu čísla A a
A XOR Bi-tého bitu čísla B podle následujících tabulek:
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 << Bposune čí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 >> Bposune čí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*c+d = (a+(b*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 zápisu 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=xN-1... x1x0 je podle definice rovna x0 XOR x1 XOR ... XOR xN-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=2k (to opět můžeme bez újmy na obecnosti předpokládat) přeuspořádat na P(x)=(x0 XOR xN/2) XOR (x1 XOR xN/2+1) XOR ... XOR (xN/2-1 XOR xN-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 log2 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

Příklad 3:

Ve vzorovém řešení úlohy P-I-4 b) jsme potřebovali přesunout posloupnost jedniček na konec čísla, tedy číslo tvaru 0i1j0k převést na 0i0k1j. To je pomocí dělení možné provést v konstantním čase třeba takto:
x=0i1j0k
a := x and (x-1) a=0i1j-100k  (viz Příklad 1)
b := x + a b=0i0j-110k
y := x / b b=0i0k1j

Zde jsme využili toho, že dělení mocninou dvojky je možné použít jako bitový posun doprava, ovšem zadaný místo počtu bitů, o které se má posouvat, číslem majícím 1 na pozici, která se má po posunu objevit úplně vpravo.