Matematická olympiáda – kategorie P

Zadání úloh domácí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ů.

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.

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 Ti, 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 Ti 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 a1 až aN, přičemž ai 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ž 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
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:8
A OR BVyhodnocují se tak, že se i-tý bit výsledku spočte z i-tého bitu čísla A a7
A XOR Bi-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 << 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 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=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

Soutěžní úlohy

  1. Sestrojte program pro ALIK, jehož výsledkem bude počet jedničkových bitů ve dvojkovém zápisu čísla na vstupu.
  2. 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ý.