Matematická olympiáda – kategorie P

Zadání úloh domácího kola 64. ročníku

Úlohy P-I-1 a P-I-2 jsou praktické, vaším úkolem v nich je vytvořit a odladit efektivní program v jazyce Pascal, C nebo C++. Řešení těchto dvou úloh odevzdávejte ve formě zdrojového kódu přes webové rozhraní přístupné na stránce http://mo.mff.cuni.cz/submit/, kde také naleznete další informace. Odevzdaná řešení budou automaticky vyhodnocena pomocí připravených vstupních dat a výsledky vyhodnocení se dozvíte krátce po odevzdání. Pokud váš program nezíská plný počet 10 bodů, můžete své řešení opravit a znovu odevzdat.

Úlohy P-I-3 a P-I-4 jsou teoretické. V úloze P-I-3 je vaším úkolem nalézt efektivní algoritmus řešící zadaný problém. Řešení úlohy se skládá z popisu navrženého algoritmu, zdůvodnění jeho správnosti (funkčnosti) a také odhadu časové a paměťové složitosti. Součástí řešení úlohy P-I-3 je i zápis navrženého algoritmu ve formě zdrojového kódu nebo pseudokódu. V úloze P-I-4 je potřeba popsat požadovanou magickou síť a dokázat, že splňuje zadané vlastnosti; pokud požadovaná síť neexistuje, je nutné její neexistenci zdůvodnit. Řešení obou teoretických úloh odevzdávejte ve formě souboru typu PDF přes výše uvedené webové rozhraní.

Řešení všech úloh můžete odevzdávat do 15. listopadu 2014. Opravená řešení a seznam postupujících do krajského kola najdete na webových stránkách olympiády na adrese http://mo.mff.cuni.cz/, kde jsou také k dispozici další informace o kategorii P.

P-I-1 Mezery

Textové editory a obdobné programy pro přípravu textů se snaží, aby jimi vytvořené texty vypadaly esteticky co nejlépe. Podíváte-li se například na toto zadání, všimnete si, že konce všech řádků v odstavci kromě posledního jsou zarovnané přesně pod sebou. Aby toto bylo možné, ne všechny mezery mají stejnou šířku. Je ovšem nežádoucí, aby na některém řádku byly mezery příliš široké nebo naopak příliš úzké. Proto může být vhodné také změnit zalomení řádků. Editory samozřejmě berou do úvahy i další možnosti a omezení (rozdělování slov, řádek by neměl končit předložkou apod.), kterými se ale pro účely této úlohy nebudeme zabývat.

Soutěžní úloha

Je zadán odstavec textu. Určete jeho rozdělení na řádky tak, aby velikosti mezer byly co nejbližší jejich optimální hodnotě.

Formát vstupu

Vstupem je posloupnost slov (složených pouze z malých a velkých písmen latinské abecedy) oddělených mezerami či konci řádků. Každý řádek obsahuje nanejvýš 200 znaků, každé slovo má nejvýše 29 písmen. Celý text má nejvýše 100 000 slov.

Formát výstupu

Výstupem je posloupnost vstupních slov ve stejném pořadí, lišící se pouze rozložením na řádky. Délka každého řádku výstupu smí být nejvýše 60 znaků (včetně mezer) a na každém řádku kromě posledního musí být alespoň dvě slova.

Bodování

Pokud vaše řešení neskončí pro některý z testovacích vstupů v časovém limitu či jeho výstup nesplňuje dané podmínky, nezíská za tento testovací vstup žádné body.

Jinak pro každý řádek výstupu kromě posledního určíme šířku mezer tímto způsobem (který předpokládá, že délka řádku je 60 a všechna písmena mají stejnou šířku 1):

šířka mezer = (60 - (počet písmen na řádku)) / ((počet slov na řádku) - 1)

Dále určíme chybu řádku tímto způsobem (za každou mezeru započítáme druhou mocninu její odchylky od optimální šířky 1; díky použití druhé mocniny podstatně více penalizujeme neesteticky vypadající velké mezery):

chyba = (počet slov na řádku - 1) · (šířka mezer - 1)2.

Chyba celého odstavce je součet chyb jeho řádků. Vaše řešení pak za tento testovací vstup obdrží

(1 + chyba optimálního řešení) / (1 + chyba vašeho řešení) bodů

Body za všech 10 testovacích vstupů pak sečteme a výsledek zaokrouhlíme na nejbližší celé číslo.

V sedmi z testovacích vstupů bude mít text nejvýše 1 000 slov. Ve třech z nich bude mít optimální řešení nejvýše 5 řádků.

Příklad

Pro vstup

Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi sed ullamcorper
laoreet nisl Nunc tincidunt felis sed purus tristique a venenatis leo auctor
Nam vel ultrices enim nec mattis erat Vestibulum vestibulum urna quis
convallis accumsan sapien tortor aliquet massa a mattis ipsum lorem eget
tellus Praesent sollicitudinidorcivenenatis pulvinar Aliquam vitae
ullamcorper diam

je optimální následující výstup:

Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi
sed ullamcorper laoreet nisl Nunc tincidunt felis sed purus
tristique a venenatis leo auctor Nam vel ultrices enim
nec mattis erat Vestibulum vestibulum urna quis convallis
accumsan sapien tortor aliquet massa a mattis ipsum lorem
eget tellus Praesent sollicitudinidorcivenenatis pulvinar
Aliquam vitae ullamcorper diam

Jeho první řádek má 8 mezer délky 1.000, druhý má 8 mezer délky 1.125, třetí má 8 mezer délky 1.750, čtvrtý má 7 mezer délky 1.429, pátý má 8 mezer délky 1.375 a šestý (tedy předposlední) má 4 mezery délky 1.750. Celková chyba tedy je 8 · 0.0002 + 8 · 0.1252 + 8 · 0.7502 + 7 · 0.4292 + 8 · 0.3752 + 4 · 0.7502 ≈ 9.286.

Naproti tomu vydá-li vaše řešení výstup

Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi
sed ullamcorper laoreet nisl Nunc tincidunt felis sed purus
tristique a venenatis leo auctor Nam vel ultrices enim nec
mattis erat Vestibulum vestibulum urna quis convallis
accumsan sapien tortor aliquet massa a mattis ipsum lorem
eget tellus Praesent sollicitudinidorcivenenatis pulvinar
Aliquam vitae ullamcorper diam

s celkovou chybou 12.111 (první řádek 8 mezer délky 1.000, druhý 8 mezer délky 1.125, třetí 9 mezer délky 1.222, čtvrtý 6 mezer délky 2.167, pátý 8 mezer délky 1.375 a šestý 4 mezery délky 1.750), získá za něj 0.785 bodu. Kdyby stejně úspěšně řešilo všech 10 testovacích vstupů, získá 8 bodů.

P-I-2 Rušení stanic

Radní v Kocourkově řeší problém, proč jsou poslední dobou obyvatelé města tak bledí. Napadlo je, že za to může nedostatek sluníčka. Proto se rozhodli, že zruší ve městě metro a lidé budou nuceni strávit víc času venku. Aby však změna nebyla pro obyvatele příliš náhlá, rozhodli se, že budou metro rušit postupně po jednotlivých stanicích. Navíc by chtěli, aby zbylá síť metra i po zrušení několika stanic zůstala souvislá – tedy aby se mezi každými dvěma zbylými stanicemi bylo možné dopravit (třeba i s několika přestupy), aniž by bylo potřeba projet zrušenou stanicí. Pomůžete radním rozhodnout, v jakém pořadí mají rušit stanice metra?

Soutěžní úloha

Je zadána souvislá síť metra s N stanicemi očíslovanými od 1 do N a s M obousměrnými linkami mezi některými dvojicemi stanic. Vypište čísla všech stanic v pořadí, ve kterém by bylo možné je ze sítě postupně odebírat, aniž by zbývající síť v kterémkoli okamžiku přestala být souvislá.

Formát vstupu

Program čte vstupní data ze standardního vstupu. První řádek obsahuje dvě celá čísla N, M oddělená mezerou (N ≥ 1, M ≥ 0), udávající po řadě počet stanic a počet linek v síti. Každý z následujících M řádků obsahuje dvě celá čísla od 1 do N, udávající dvojici stanic, které jsou spojeny linkou. Můžete předpokládat, že žádná linka se ve vstupu neobjeví dvakrát a žádná stanice není spojena sama se sebou.

Formát výstupu

Program vypíše na standardní výstup jediný řádek. Na něm bude N mezerami oddělených čísel udávajících pořadí, v jakém mají být stanice odstraněny. Pokud je více možných řešení, vypište libovolné z nich.

Příklad

Vstup:
5 4
1 2
2 3
3 4
4 5

Výstup:
1 2 3 4 5

Další možná řešení jsou například 5 4 3 2 1, 5 1 4 2 3 nebo 1 2 5 3 4.

Vstup:
7 10
1 4
4 5
5 1
5 2
2 3
3 4
2 6
5 7
2 7
6 7

Výstup:
1 4 5 3 7 2 6

Uvedený výstup je jednou z mnoha správných odpovědí.

Bodování

Plných 10 bodů obdrží správné řešení, které efektivně vyřeší libovolný vstup s N ≤ 1 000 000 a M ≤ 10 000 000. Až 5 bodů získá správné řešení, které efektivně vyřeší libovolný vstup s N ≤ 1 000 a M ≤ 10 000.

P-I-3 Ztracený paket

Při přenosu velkých souborů po síti je nutné je rozdělit na menší kusy (pakety), které jsou doručovány samostatně. Při doručování není zaručeno zachování pořadí paketů. Aby je přijímající počítač dokázal správně spojit, pakety jsou očíslovány od 1 do n dle pořadí, v jakém po sobě následují v souboru.

Na přijímající počítač zatím dorazilo n-1 z n odeslaných paketů, jeden se tedy ztratil. Abychom mohli odesílající počítač požádat o jeho znovuzaslání, potřebujeme určit číslo tohoto ztraceného paketu. Přijaté pakety jsme zatím neměli čas nijak zpracovat, máme je pouze uloženy na disku v pořadí, v jakém dorazily. Paketů je mnoho, nemůžeme si proto všechna jejich čísla uložit do paměti. Čtení dat z disku je ovšem pomalé a chceme jej minimalizovat.

Formát vstupu

Váš program čte data ze vstupního souboru pakety.txt. Na jeho prvním řádku je přirozené číslo n (1 ≤ n ≤ 1 000 000 000). Na každém z n-1 následujících řádků je jedno přirozené číslo v rozsahu 1 až n včetně, udávající číslo paketu. Každé číslo paketu se v souboru vyskytuje nejvýše jednou, pořadí čísel paketů ve vstupním souboru může být libovolné.

Formát výstupu

Výstupem je přirozené číslo v rozsahu 1 až n včetně, které se nevyskytuje mezi čísly paketů ve vstupním souboru.

Příklad

Vstup:
6
2
4
1
6
5

Výstup:
3

Bodování

Přijatelná jsou pouze řešení, jejichž proměnné na běžném počítači používají nanejvýš 10 kB paměti (do tohoto limitu se počítá i dynamicky alokovaná paměť a zásobník návratových hodnot v rekurzivních programech; naopak se do něj nepočítají vnitřní proměnné standardních knihoven apod.).

Plných 10 bodů obdrží takové řešení, které přečte vstupní soubor právě jednou a nepoužívá žádné další pomocné soubory. Až 7 bodů může obdržet řešení, které přečte vstupní soubor (či pomocné soubory srovnatelné velikosti) nejvýše 300krát. Libovolné jiné přijatelné řešení může obdržet až 4 body.

P-I-4 Magická síť

K této úloze se vztahuje studijní text uvedený na následujících stranách. Doporučujeme nejprve prostudovat studijní text a až potom se vrátit k samotným soutěžním úlohám.

Soutěžní úloha

Úkol 1: Nechť NAE(x,y,z) je omezení předepisující, že proměnné x, y a z nemají všechny stejnou hodnotu. Nechť ONE(x) je omezení předepisující, že proměnná x má hodnotu 1. Nalezněte síť, používající pouze omezení typu NAE a ONE, která simuluje OR.

Úkol 2: Nalezněte síť, používající pouze omezení typu NAE, která simuluje EQ(a,b), kde a a b jsou navzájem různé proměnné.

Úkol 3: Ukažte, že pomocí NAE nelze simulovat OR.

Studijní text

Magická síť se skládá z omezení a proměnných. Každá proměnná může nabývat hodnot 0 nebo 1. Omezení pak předepisují podmínky, které ohodnocení proměnných musí splňovat. Například omezení XOR(x,y,z) předepisuje, že z proměnných x, yz jich lichý počet musí mít hodnotu 1, omezení OR(x,y,z) předepisuje, že alespoň jedna z x, yz musí mít hodnotu 1, omezení EQ(x,y) předepisuje, že xy musí mít stejnou hodnotu, a podobně. Proměnné se v jednom omezení mohou opakovat.

Některé z proměnných jsou vstupní a můžeme jim nastavit konkrétní hodnotu. Po seslání příslušného zaklínadla se pak ostatním proměnným nastaví takové hodnoty, aby všechna omezení byla splněna. Pokud žádná taková volba hodnot neexistuje, zaklínadlo nás na to upozorní. V prvním případě říkáme, že magická síť zadaný vstup přijímá, ve druhém ho odmítá. Magická síť simuluje omezení O, jestliže přijímá právě stejné hodnoty proměnných jako omezení O.

Příklad 1: Magickou síť zapisujme jako seznam typů omezení, k nimž do závorek budeme připisovat proměnné, na které jsou aplikovány. Síť XOR(a,b,c), XOR(b,c,d) tedy vynucuje, že lichý počet z proměnných a, b a c má hodnotu 1 a že lichý počet z proměnných b, c a d má hodnotu 1.

Nechť a a d jsou vstupní proměnné této sítě. Jestliže a má hodnotu 0, pak právě jedna z proměnných b a c musí mít hodnotu 1, a proto d musí mít hodnotu 0. Naopak, má-li a hodnotu 1, pak hodnota proměnné b musí být stejná jako hodnota proměnné c, a proto d musí mít hodnotu 1.

Tato magická síť tedy přijímá právě ty vstupy, kde a a d mají stejnou hodnotu, a simuluje tedy omezení EQ(a,d).

Obecněji: Typicky nás bude zajímat, která omezení jdou vyjádřit pomocí jiných. Říkáme, že množina typů omezení {O1, O2, …, On\} simuluje omezení O, jestliže existuje magická síť používající pouze omezení typu O1, O2, …, On, která simuluje O. Příklad 1 tedy ukazuje, že XOR simuluje EQ.

Omezení O(x1, …, xn) nazveme slabé, jestliže zakazuje právě jednu kombinaci hodnot proměnných x1, …, xn. Slabé omezení budeme zapisovat jako Sh1h2hn, kde h1, …, hn jsou hodnoty proměnných, které zakazuje. Třeba omezení S001(x,y,z) je splněno, jestliže x=1 nebo y=1 nebo z=0, a omezení S000 je stejné jako OR. Nechť SATn označuje množinu všech slabých omezení s právě n proměnnými.

Příklad 2: SAT3 simuluje XOR, jelikož síť

S000(x,y,z), S011(x,y,z), S101(x,y,z), S110(x,y,z)

zakazuje všechny kombinace hodnot proměnných x, y a z, v nichž se hodnota 1 vyskytuje suděkrát.

Příklad 3: Množina omezení SAT2 nesimuluje OR. Abychom si to dokázali, zaveďme si nejprve funkci maj se třemi vstupy. Ta bude vracet ten vstup, který se vyskytuje nejčastěji (proto se jí také někdy říká majorita). Tedy třeba maj(1,1,1) = maj(1,0,1) = 1 a maj(0,0,1) = 0.

Uvažujme nyní libovolnou síť s omezeními z množiny SAT2. Nechť x1, …, xn jsou proměnné této sítě. Řekněme, že by tato síť simulovala OR(x1,x2,x3). Jelikož omezení OR je splněno pro hodnoty 1, 0 a 0, existuje nějaké přiřazení hodnot proměnným, které splňuje všechna omezení, x1 má hodnotu 1 a x2 a x3 mají hodnoty 0. Nechť ai označuje hodnotu proměnné xi v tomto přiřazení, pro i=1, …, n. Obdobně existuje přiřazení s hodnotami bi splňující všechna omezení takové, že b2 = 1 a b1 = b3 = 0, a přiřazení s hodnotami ci splňující všechna omezení takové, že c3 = 1 a c1 = c2 = 0.

Uvažme ohodnocení s hodnotami di = maj(ai,bi,ci). Tvrdíme, že di také splňuje všechna omezení: Mějme nějaké omezení Sh1h2(xi,xj) ze sítě. Pokud ai = bi a aj = bj, pak di = maj(ai,ai,ci) = ai a dj = maj(aj,aj,cj) = aj splňuje podmínku Sh1h2, protože ji splňuje ai a aj. Proto předpokládejme, že ai ≠ bi nebo aj ≠ bj, a obdobně ai ≠ ci nebo aj ≠ cj a stejně tak bi ≠ ci nebo bj ≠ cj. Ze symetrie mezi i a j a mezi ohodnoceními a, b a c stačí uvažovat případ, že ai ≠ bi a ai ≠ ci. Z toho odvodíme, že bi = ci, a proto bj ≠ cj. Díky symetrii mezi b a c pak stačí uvažovat případ, že aj = bj a aj ≠ cj. Pak ale maj(ai,bi,ci) = maj(ai,bi,bi) = bi a maj(aj,bj,cj) = maj(bj,bj,cj) = bj, a proto di = bi a dj = bj splňuje podmínku Sh1h2.

Povšimněme si, že d1 = maj(1,0,0) = 0 a obdobně d2 = d3 = 0. Ale omezení OR(x1, x2, x3) předepisuje, že alespoň jedna z proměnných x1, x2 a x3 má hodnotu 1, a proto v každé magické síti simulující OR(x1,x2,x3) musí přiřazení hodnot di proměnným porušovat nějaké omezení. Uvažovaná síť tedy nesimuluje OR(x1,x2,x3).