Druhá série dvacátého prvního ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Zadání úloh

Druhá série dvacátého prvního ročníku KSP

Matfyzák

Po autentické reportáži z pekla, která nás stála jednoho reportéra, jsme se rozhodli držet při zemi (resp. na zemi). Téma druhé série se ponese ve znamení věrného popisu matfyzácké reality. Jak vypadá běžný den matfyzáka vám popíší přímo ti nejkvalifikovanější – Jan Bulánek a Zbyněk Falt.

Jdu temným lesem, když tu najednou za sebou uslyším plíživé kroky. Neotáčím se a pomalu zrychluji. Ale kroky se stále blíží a když už téměř utíkám, uslyším hluboký hlas: „Definuj Lebesgueův integrál!“ V tu chvíli mi ztuhne krev v žilách, snažím se vykrucovat, ale hlas je neústupný. Během vteřiny mi před očima proběhne celý můj čtyřletý matfyzácký život a pomalu se s ním loučím …

„O-ou,“ ozve se náhle, „jdeš dneska do školy?“ Zvedám hlavu otlačenou od klávesnice. Spolubydlící mi píše na ICQ.

„Jasně, že jdu!“ odepisuji.

A tak mi začíná další všední den – den matfyzáka.

Vypiji dva dny starou kávu, která chutná spíš jako polévka, která byla v hrnku před ní, a pomalu se přesunu k umyvadlu. Zbytkem kartáčku si vyčistím zuby a podívám se do zrcadla, jenže hřeben nikde. Tak aspoň polituji všechny, kteří mě dnes uvidí. Holicímu strojku se jenom zasměji a jdu se oblékat. Děravé ponožky, tenisky vylepšené o několik ergonomických děr, tradiční ledvinka. Když ale zpoza postele vyndávám své oblíbené tričko, nestačím se divit. Kdysi krásně bílé, nyní hýří barvami. Ale asi nic divného, když na něj něco tu a tam ukápne.

21-2-1 Špinavé tričko (10 bodů)

Takové tričko si lze představit jako obdélník a skvrny si lze rovněž představit jako obdélníky různých barev, které se mohou vzájemně překrývat. Pokud se na jednom místě překrývá více skvrn, je na tomto místě vidět pouze ta skvrna, která se na tričku objevila jako poslední. Vaším úkolem bude pro zadané skvrny spočítat, kolik které barvy se na tričku vyskytuje a kolik ještě zbylo nezašpiněného trička.

Na vstupu dostanete kladná celá čísla W a H, která představují šířku a výšku trička. Levý dolní roh bude mít souřadnice [0,0] a pravý horní roh souřadnice [W,H]. Dále dostanete číslo N, které představuje počet skvrn, ty jsou na vstupu zadávány přesně v tom pořadí, v jakém se objevovaly na tričku. Každá skvrna je zadána pěti kladnými celými čísly. Souřadnicemi levého dolního rohu, souřadnicemi pravého horního rohu a svou barvou. Barvy jsou očíslované od 1 do N.

Příklad: Pro W=6, H=6, N=3 a skvrny (1, 1, 5, 5, 2), (1, 2, 2, 3, 1) a (4, 4, 6, 6, 3) bude výstup, že čistého trička zůstalo 16 čtverečních jednotek, barva 1 zabírá 1 jednotku, barva 2 zabírá 14 jednotek a barva 3 se vyskytuje na 4 jednotkách.

Konečně mohu vyrazit z kolejí, doběhnout autobus a nestihnout tramvaj. Však pojede další a škola počká. V tramvaji se snažím vyřešit domácí úkol z diskrétní matematiky. Ještě, že je tak jednoduchý. Ale i tak se postaral na celou cestu o můj typický matfyzácký nepřítomný pohled, který se změnil až ve chvíli, kdy jsem o 4 zastávky přejel Malostranské náměstí. Konečně přijíždím ke škole. Místo na přednášku ale směruji své kroky k rotundě, ve které je počítačová laboratoř, abych se podíval, kde že to vlastně mám přednášku. Zrovna jsem stál uprostřed, když mě polil studený pot. Ta noční můra měla být varováním, neboť na dnešek jsem měl od profesora už po několikáté slíbeno, že mě z té analýzy vyzkouší, ať chci nebo nechci. Tentokrát ale jeho výraz nasvědčoval tomu, že to myslí smrtelně vážně …

Řešení

21-2-2 Útěk před zkouškou (9 bodů)

Rotunda má tvar kruhu. Náš hrdina se nachází přesně uprostřed, zatímco profesor na jeho obvodu. Protože je podél stěn rotundy mnoho skříní, stolů a východů, stačí, aby se student dostal k libovolnému bodu na obvodu, odkud již může utéct nebo se bezpečně schovat. Samozřejmě, že se zároveň na tomto bodu nesmí vyskytovat i profesor (pak by se velmi těžko schovávalo a student by byl okamžitě vyzkoušen). Má to ale jeden háček, matfyzák nezvyklý pohybu se pohybuje 4× pomaleji než rozzlobený profesor. Profesor se ale na druhou stranu z neznámého důvodu bojí přiblížit ke středu, takže se pohybuje pouze podél obvodu.

Najděte strategii, jak se má za těchto podmínek student pohybovat, aby profesorovi vždy utekl, nebo dokažte, že mu utéct nelze. Profesor se může pohybovat zcela libovolně, takže o jeho „chytací“ strategii nemůžete dělat žádné předpoklady.

Ani nevím, jestli se mi podařilo utéct nebo ne. Každopádně mi z toho pořádně vyhládlo. Takhle se přeci nemohu soustředit. A tak jsem se odhodlal k zoufalému činu. Vydal jsem se do menzy. Bohužel jsem vůbec nebyl sám, kdo dostal hlad, takže před výdejnou byla obrovská fronta.

Řešení

21-2-3 Fronta (10 bodů)

Matfyzáci jsou pyšní na svou inteligenci a dávají to ostatním najevo. Nejvíce se tento problém projevuje, když jsou matfyzáci nuceni tvořit fronty. Matfyzák, který si o jiném matfyzákovi myslí, že je hloupější, odmítá stát ve frontě za ním. Tím vzniká řada nepříjemných strkanic a šarvátek.

Napište program, který dostane seznam matfyzáků a jejich názorů na inteligenci ostatních. Vaším úkolem je matfyzáky uspořádat do posloupnosti tak, aby vždy platilo, že pokud považuje matfyzák A kolegu B za hloupějšího, pak musí v této posloupnosti stát A před B. Samozřejmě, že takové uspořádání nemusí existovat. Např. když si všichni myslí, že jsou chytřejší než všichni ostatní. V takovém případě oznamte, že uspořádání nelze vytvořit.

Tato úložka je praktická, což znamená, že řešení budete odevzdávat výhradně formou odladěného zdrojového kódu. Přesnější zadání a formulář na odevzdání kódu nalzenete jako vždy v CodExu. Nevíte-li, co praktická úložka je a jak přesně postupovat, podívejte se do zadání úlohy 21-1-2 „Optimalizace kotlů“.

Ještě, že to (jako ostatně vždy) vyšlo tak, že jsem šel na řadu první, takže jsem mohl nerušeně pokračovat ve studiu. Tříhodinové zkoušení Unreal Tournamentu v rámci předmětu „Vývoj počítačových her“ mi vždycky šlo a na rozdíl od jiných předmětů jsem v něm viděl svou budoucnost. Bohužel někdo vždycky rozpojí pracně vytvořenou síť, takže počítače musíme každý týden sesíťovávat znovu a znovu. A to zavání nepříjemnou fyzickou prací.

Řešení

21-2-4 Síťování (8 bodů)

Sesíťovat počítače není žádná maličkost. Nemají totiž klasické síťové rozhraní. Každý počítač má dvě zdířky na síťový kabel. Jednu vstupní a jednu výstupní. Pokud tedy chcete dosáhnout konektivity mezi všemi počítači, musí být spojeny do kruhu, a to tak, že každý kabel vede z výstupní zdířky jednoho počítače do vstupní zdířky druhého počítače. Navíc jsou kabely špatně odstíněné, takže se nesmí nikde křížit, aby se navzájem nerušily.

Na vstupu dostanete číslo N, které značí počet počítačů v místnosti. Následuje N řádků, přičemž i-tý řádek určuje souřadnice i-tého počítače v místnosti. Vaším úkolem je najít pořadí počítačů p1, p2, … , pn, takové, že se v něm každý počítač vyskytuje právě jednou a úsečky (p1,p2),(p2,p3), … , (pn-1, pn), (pn, p1) se nikde neprotínají. Pokud to není možné, vypište, že řešení neexistuje.

Například pro N=4 a souřadnice (0, 0), (0, 2), (1, 1) a (-1, -2) může být výstupem třeba (2, 3, 4, 1).

Když jsme po sedmi hodinách studia uznali, že už umíme dost a že se nám dělají mžitky před očima, vydal jsem se domů. Na kolejích na mě ale čekalo nepříjemné překvapení. Naše nádobí mi totiž div nepřišlo otevřít dveře. Už jednou jsme se pokoušeli tuto situaci teoreticky řešit, ale očividně bezúspěšně. Sice by se zdálo, že nejsnazší je všechno nádobí prostě umýt, ale na co bychom pak studovali informatiku?

Řešení

21-2-5 Nádobí (10 bodů)

Umývání nádobí je velice náročná činnost, takže lze umýt pouze jeden kus za jeden den. Bohužel ale platí, že když některý kus neumyjete do určité doby, nemá smysl jej umývat vůbec a je mnohem ekonomičtější vyhodit jej a koupit nový kus. Samozřejmě, že za ta léta už studenti vědí, kolik dní určité kusy vydrží bez umytí, i kolik takový kus stojí nový.

Vaším úkolem bude navrhnout optimální systém umývání nádobí takový, aby student musel za nákup nového nádobí zaplatit co nejméně. Na vstupu dostanete číslo N, které představuje počet kusů nádobí. Dále N dvojic čísel Di a Ci, což znamená, že i-tý kus vydrží ještě Di dní a nový stojí Ci korun.

Vypište, v jakém pořadí se má nádobí umývat (jeden kus za jeden den) tak, aby se umyly/koupily všechny kusy a zároveň náklady na nákup byly minimální.

Například pro vstup N=3 a dvojice (1, 5), (1, 4) a (2, 3) je správný výstup (1, 3, 2). Což znamená, že umyjeme 1. a 3. kus. Druhý kus už bohužel nestihneme umýt včas, a tak jej budeme muset koupit nový. Všimněte si, že jakmile nestihneme druhý úkol, už není kam spěchat a raději si uděláme třetí, za který díky tomu nezaplatíme pokutu. Náklady na nákup nového nádobí jsou 4 koruny.

Konečně si mohu do nového hrnku uvařit oblíbenou čínskou polévku a jít se podívat, kdo je online. No jo, noc bude ještě dlouhá. Navíc je potřeba zhlédnout nový díl Simpsonových. Po několika hodinách začínám cítit, že bych měl jít spát. Ale co, ještě jeden díl určitě vydržím …Zzz

Jdu temným lesem, když tu najednou …

Řešení

21-2-6 Nejkratší opět vyhrává (12 bodů)

Tuto úlohu musíte řešit v programovacím jazyce RAPL, jehož popis najdete v zadání úlohy 21-1-6 z minulé série. Taktéž doporučujeme přečíst si řešení této úlohy, vyvarujete se tak častých chyb.

Úloha 1 [5 bodů]: V libovolném pořadí dostanete čísla v rozsahu 1 až N, každé právě jednou, až na jedno, které chybí. Vaším úkolem je chybějící číslo nalézt.

Číslo 1 ≤ N < 232 je po spuštění programu uloženo v registru n a čísla A[0] až A[N-2] jsou čísla v rozsahu 1 až N, každé se vyskutuje nejvýše jednou. Vypište to jediné číslo v rozsahu 1 až N, které mezi těmito čísly chybí. Váš program musí doběhnout v lineárním čase vzhledem k N a musí použít pouze konstantně mnoho paměti nezávisle na velikosti N, přičemž pole A je pouze pro čtení. Vaším cílem je napsat nejkratší program, který splňuje všechny tyto podmínky.

Úloha 2 [7 bodů]: Kromě toho, že nechybí jedno, ale dvě čísla, je tato úloha stejná jako předchozí.

Přesně řečeno, na začátku dostanete v registru n číslo 2 ≤ N < 232. Vaším úkolem je v libovolném pořadí vypsat tu jedinou dvojici čísel z rozsahu 1 až N, která se nevyskytuje mezi čísly A[0] až A[N-3]. Váš program musí doběhnout v lineárním čase vzhledem k N a musí použít pouze konstantně mnoho paměti nezávisle na velikosti N, přičemž pole A je pouze pro čtení. Vaším cílem je napsat nejkratší program, který splňuje všechny tyto podmínky.

Řešení