Na řešení úloh máte 4,5 hodiny čistého času. Řešení každé úlohy pište na samostatný list papíru. Při soutěži je zakázáno používat jakékoliv pomůcky kromě psacích potřeb (tzn. knihy, kalkulačky, mobily, apod.).
Řešení každého příkladu musí obsahovat:
Za každou úlohu můžete získat maximálně 10 bodů. Hodnotí se nejen správnost řešení, ale také kvalita jeho popisu (včetně zdůvodnění správnosti) a efektivita zvoleného algoritmu. Algoritmy posuzujeme podle jejich časové složitosti, tzn. podle závislosti doby výpočtu na velikosti vstupních dat. Záleží přitom pouze na řádové rychlosti růstu této funkce. V zadání každé úlohy najdete limity na velikost vstupních dat. Můžete je využít k odhadu, jak dobré je vaše řešení. Na počítači pracujícím rychlostí miliarda instrukcí za sekundu dokončí vzorové řešení výpočet s libovolnými povolenými vstupními daty nejvýše za několik sekund.
Nejprve si připomeňme, že pojem medián posloupnosti liché délky označuje její prvek prostřední podle velikosti. Jinými slovy, je to ten prvek, který by byl přesně uprostřed, kdybychom danou posloupnost uspořádali. Například mediánem posloupnosti (3,1,4,1,5) je číslo 3 a mediánem posloupnosti (9,2,6,5,3,5,8) je číslo 5.
Po mnoho let se hledala odpověď na základní otázku života, vesmíru a vůbec. Nakonec tuto odpověď počítač k tomu určený skutečně vypočítal. Byla však poměrně překvapivá: 42. Až tehdy mnozí pochopili, že raději než odpověď měli hledat samotnou otázku.*Pokud vám tato slova nic neříkají, doporučujeme vám knihu od Douglase Adamse s názvem Stopařův průvodce po galaxii (v originále The Hitchhiker's Guide to the Galaxy). S řešením této úlohy vám znalost knihy samozřejmě nijak nepomůže.
Napište program na zjištění, kolik má tato posloupnost souvislých podposloupností, které mají lichou délku a zároveň medián rovný 42.
Vstup: 10 -5 13 42 88 37 41 43 100 50 72 Výstup: 6
Je to těchto 6 podposloupností: (42), (42,88,37), (42,88,37,41,43), (13,42,88), (13,42,88,37,41,43,100) a (-5,13,42,88,37,41,43,100,50).
Úmyslně neuvádíme žádné omezení na velikost hodnoty n. Váš program dostane tím více bodů, čím lepší bude jeho časová složitost vzhledem k n.
Z krajského kola znáte zloděje, který si ze své loupežné výpravy odnesl sbírku modelů vesmírných lodí a chystá se ji prodat překupníkovi na černém trhu. Chce za ni dostat přesně s korun. Číslo s je kladné a celé.
Při placení se užívá n druhů mincí. Každý druh mincí má kladnou celočíselnou hodnotu. Všechny tyto hodnoty jsou poměrně malé. Placení probíhá stejně jako v běžném obchodě: Kupující nemusí zaplatit přesnou částku. Může zaplatit více a následně si nechat od prodávajícího vrátit nazpět rozdíl. Předpokládáme, že prodávající i kupující mají dostatečný počet kusů od každého druhu mincí.
Zloděj i tentokrát spěchá, a proto chce, aby celá obchodní transakce proběhla co nejrychleji. Platba částky s se musí provést tak, aby celkový počet kusů mincí použitých při placení byl co nejmenší.
Na prvním řádku vstupu je zadána celočíselná hodnota s, kterou chce zloděj dostat, a počet druhů mincí n. Druhý řádek obsahuje kladná celá čísla c1, c2, .., cn – hodnoty jednotlivých druhů mincí. Tyto hodnoty jsou uspořádány vzestupně. Navíc je vždy c1=1, aby bylo možné zaplatit libovolnou částku.
Program vypíše na výstup dva řádky, z nichž každý obsahuje n čísel. Na prvním řádku bude pro každý druh mince uveden počet kusů, které použije překupník na zaplacení, na druhém řádku budou podobným způsobem zapsány počty mincí, které zloděj překupníkovi vrátí nazpět. Pořadí vypsaných hodnot bude odpovídat pořadí mincí ze vstupu.
Pokud existuje více řešení s optimálním celkovým počtem použitých mincí, nalezněte jedno libovolné z nich.
Vstup: 8 4 1 2 5 10 Výstup: 0 0 0 1 0 1 0 0
Částka 8 se jednou mincí zjevně zaplatit nedá, ale dvěma mincemi to už jde: překupník zaplatí 10 a zloděj mu vrátí 2.
Vstup: 10 3 1 5 6 Výstup: 0 2 0 0 0 0
Dbejte na to, aby vaše řešení bylo v první řadě korektní – tedy aby vždy našlo optimální způsob placení. Nekorektní řešení budou hodnocena velmi přísně.
U většiny typů řešení je důležitou součástí řešení důkaz jeho správnosti. Za řešení bez uvedeného důkazu můžete ztratit značnou část bodů (podle toho, nakolik správnost řešení je nebo není zjevná).
V letošním ročníku olympiády se setkáváme se zlomkovými programy. Ve studijním textu uvedeném za zadáním této úlohy je popsáno, jak zlomkové programy pracují a jak se programují. Studijní text je identický s textem z domácího a krajského kola.
a) Medián (3 body). Na vstupu je číslo n tvaru 2x 3y 5z, přičemž x,y,z≥0. Napište program, který ho převede na číslo 7median(x,y,z).
Mediánem tří čísel je prostřední z nich podle velikosti. Kupříkladu:
median(2,5,8) = 5,
median(8,2,5) = 5,
median(3,3,7) = 3,
median(3,2,3) = 3.
Váš program tedy například číslo n=28 32 55 převede na číslo 75.
b1) Kvadrát (3 body). Na vstupu je číslo n tvaru 2x ·47, přičemž x≥0. Napište program, který ho převede na číslo 3(x2).
Tedy například:
b2) Odmocnina (7 bodů). Na vstupu je číslo n tvaru 2x, přičemž x≥0. Napište program, který ho převede na číslo 3y, kde y=⌈sqrt(x)⌉.
Značení ⌈z⌉ představuje horní celou část čísla z, tzn. nejmenší celé číslo, které je větší nebo rovné z. Například ⌈4,7⌉= 5, ⌈47⌉= 47, ⌈sqrt(16)⌉= ⌈4 ⌉= 4 a ⌈sqrt(22)⌉= 5.
Proto:
Při hodnocení úlohy bude přihlédnuto také k časové složitosti vašich zlomkových programů, tzn. k počtu kroků výpočtu v závislosti na parametrech x, y a z. Pokud bude váš program provádět řádově více kroků než vzorové řešení, dostanete nejvýše 2 body za podúlohu a, nejvýše 2 body za podúlohu b1, resp. 4–6 bodů za podúlohu b2.
Zlomkové programy slouží k výpočtu některých funkcí na přirozených číslech. Zlomkový program má velmi jednoduchý zápis – je to konečná posloupnost zlomků, tedy kladných racionálních čísel (z1,..,zk).
Výpočet zlomkového programu probíhá po jednotlivých krocích. Během výpočtu si udržujeme jediné celé číslo a, tzv. aktuální hodnotu. Na začátku výpočtu se tato hodnota rovná hodnotě na vstupu. V každém kroku výpočtu najdeme nejmenší i takové, že a·zi je celé číslo, a změníme aktuální hodnotu na a·zi. Pokud takové i neexistuje, výpočet končí.
Jedním takovým programem je posloupnost (1/8,9/4,3/2). Slovně si popíšeme průběh výpočtu tohoto programu: Dokud to jde, zmenšuj x o 3. Když už to nejde, máme v a číslo 1, 2, nebo 4, a převedeme ho tedy snadno na 1, 3, nebo 9.
Například pro n=1024=210 se hodnota a bude měnit takto:
210 -1-> 27 -1-> 24 -1-> 2 -3-> 3.
(Číslo nad šipkou je pořadovým číslem zlomku, kterým jsme a v daném kroku násobili.)
Pro přesnost dodejme, že velmi záleží na pořadí jednotlivých zlomků. Například program (9/4,3/2,1/8) by z čísla 2x vyrobil číslo 3x. Zlomek 1/8 by se při výpočtech tohoto programu nikdy nepoužil.
Jiné vyhovující programy jsou (1/8,3/2), (3/2,1/27) a (1/27,3/2). Rozmyslete si, proč každý z nich řeší správně Příklad 1.
Častou chybou je odpovědět, že pro vstup n=4 se tento program zacyklí, ale pro vstup n=7 se výpočet programu zastaví, neboť 7 není dělitelné dvěma. Správnou odpovědí ale je, že v obou případech poběží výpočet programu do nekonečna. Zajímají nás totiž jenom hodnoty zlomků, nikoli jejich zápis. Zlomek 2/2 představuje racionální číslo 1, takže 7·(2/2) = 7·1 je celé číslo.
Abyste se ve svých řešeních takto nespletli, doporučujeme vám psát všechny zlomky v základním tvaru. Pro posloupnost zlomků zapsaných v základním tvaru platí, že v každém kroku výpočtu hledáme nejmenší i takové, že jmenovatel i-tého zlomku dělí beze zbytku aktuální hodnotu.
Číslo zadané na vstupu je určitě sudé a není dělitelné žádným prvočíslem různým od 2. Použijeme prvočíslo 11 jako příznak, že už nejsme na začátku výpočtu. V prvním kroku tedy přepíšeme číslo 2x+1 na 2x 32 ·11. Toho dosáhneme zlomkem 32·11/2=99/2.
Jakmile se objeví v prvočíselném rozkladu aktuální hodnoty prvočíslo 11, znamená to, že první krok výpočtu máme úspěšně za sebou. Můžeme tedy dále klidně „měnit dvojky na trojky”. To můžeme zajistit například posloupností zlomků (3·13)/(2 ·11) a 11/13. Všimněte si, že nestačí použít jeden zlomek 33/22. Není-li vám jasné proč, přečtěte si ještě jednou Příklad 2.
Postupně se takto dostaneme k číslu 3x+2 11. V této situaci už stačí jenom vydělit aktuální hodnotu číslem 11 a můžeme skončit.
Musíme dát pozor na to, abychom ve zlomkovém programu výše popsané zlomky správně seřadili: (39/22,11/13,1/11,99/2). V prvním kroku výpočtu se jistě použije poslední zlomek. Od této chvíle je aktuální hodnota dělitelná číslem 11 nebo 13. Střídavě se proto používají první dva zlomky, dokud se nedostaneme do situace a=3x+2 11. Pak už se první ani druhý zlomek použít nedá. Použije se proto třetí zlomek, čímž získáme hodnotu a=3x+2 a výpočet zjevně skončí.
((3·13) / (2 ·11), 11 / 13, 1 / 11, (32·11) / 2 ).