Programátorská úloha 2 – Marble races

Zadanie

Pozerali ste niekedy Marble Olympics? Lebo rozhodne odporúčam. Malé sklenené guličky sa pretekajú v rôznych súťažiach s jediným cieľom – byť čo najrýchlejší. Vašou úlohou bude rozhodnúť tento problém raz a navždy a zistiť, ktorá gulička je najrýchlejšia.

K dispozícii máte pretekársku dráhu, na ktorú sa zmestia práve dve guličky. Tie odštartujete a rýchlejšia z nich vyhrá. Príprava a priebeh jedného takéhoto zápasu však trvá dosť dlho, preto by ste chceli minimalizovať počet pretekov, ktoré musíte zorganizovať. Samozrejme, môže vás napadnúť, že jednoducho zmeriate čas, ktorý trvá každej guličke dojsť do cieľa, tak to však nefunguje. Gulička sa totiž pri rôznych súperoch môže snažiť rôzne (naozaj si pozrite Marblelympics) a tento čas by o jej celkovej kvalite nič nehovoril. Našťastie sú ale guličky konzistentné a ak je gulička x rýchlejšia ako gulička y, tak x vyhrá každý pretek proti y. Naviac, žiadne dve guličky nie sú rovnako rýchle.

Vďaka tomuto naozaj platí, že sa dá nájsť jedinečné poradie guličiek, od tej najrýchlejšej po najpomalšiu. Ako to však spraviť? Našťastie, už máte za sebou nejaké kvalifikačné kolá, z ktorých máte dodatočnú informáciu. Presnejšie, guličky máte rozdelené na dve skupiny, v ktorých presne poznáte poradie daných guličiek. Máte teda podľa rýchlosti zoradené všetky guličky v prvej skupine aj všetky guličky druhej skupine. To však nehovorí nič o tom, ako sú na tom guličky medzi skupinami. Mohlo sa totiž stať, že do prvej skupiny ste dali polovicu najrýchlejších guličiek a v druhej sú tie najpomalšie. Takisto tam môže byť však skoro ľubovoľný mix, niektoré rýchle a niektoré pomalé v jednej skupine.

Vašou úlohou je teda využiť túto dodatočnú informáciu, zoradenie guličiek v oboch skupinách, pri riešení nasledovných podúloh.

Podúloha 1 (3 bodov)

Usporiadaním čo najmenšieho počtu pretekov nájdite najrýchlejšiu guličku. Ešte raz pripomeniem, že guličky sú rozdelené do dvoch skupín a poradie v rámci týchto skupín je známe, na jeho zistenie nemusíte robiť žiadne preteky. Môžete si to predstaviť tak, že guličky v oboch skupinách ste si uložili do radu podľa ich rýchlosti – od najrýchlejšej po najpomalšiu.

Koľko zápasov budete musieť usporiadať? Predpokladajte, že v prvej skupine je $n$ guličiek a v druhej $m$ guličiek.

Podúloha 2 (3 bodov)

Usporiadaním čo najmenšieho počtu pretekov nájdite tri najrýchlejšie guličky. Stále platí, že máte dve skupiny, v ktorých je vzájomné poradie známe.

Koľko zápasov budete musieť usporiadať? Predpokladajte, že v prvej skupine je $n$ guličiek a v druhej $m$ guličiek.

Podúloha 3 (4 bodov)

Usporiadaním čo najmenšieho počtu pretekov vytvorte poradie všetkých guličiek. Chcete teda všetky guličky usporiadať do radu zoradeného podľa ich rýchlosti – od najrýchlejšej po najpomalšiu.

Koľko zápasov budete musieť usporiadať? Predpokladajte, že v prvej skupine je $n$ guličiek a v druhej $m$ guličiek.

Podúloha 4 (5 bodov)

Túto podúlohu neriešte, kým nemáte vyriešenú podúlohu 3

Implementujte postup z predchádzajúcej podúlohy. Napíšte program, ktorý dostane dve usporiadané postupnosti čísel a zoradí ich podľa veľkosti do jednej výstupnej postupnosti. Všimnite si, že na rozdiel od guličiek, tu pracujete s konkrétnymi číslami. Je to však to isté ako pred tým, lebo program nevie, že 4 je väčšie ako 3 kým nespravíte “pretek” – porovnanie týchto dvoch hodnôt cez if 4 < 3. Pri riešení teda chcete použiť rovnaký postup ako v podúlohe 3.

Tento svoj program si môžete otestovať na úlohe Na telesnej výchove, ktorú nájdete na testovači. Na výsledky testovania pri bodovaní prihliadať nebudem, budem sa sústrediť na to, či sa vám podarilo vaše riešenie správne naprogramovať. Očakával by som však, že ak to zvládnete, nebude vám robiť problém vyriešiť túto úlohu.

Bonusová podúloha (2 body)

Ako by sa úloha zmenila, keby ste nemali dve, ale štyri skupiny guličiek usporiadaných podľa rýchlosti? Ako by ste organizovali preteky, aby ste minimalizovali ich počet? A ako táto úloha súvisí s triedením?

Riešenie a odovzdávanie

Vašou úlohou je vyriešiť všetky zadané podúlohy. Okrem podúlohy 4 sú všetky z nich teoretické a preto ma zaujíma iba slovný opis riešenia a zdôvodnenie správnosti.

Popis spolu s programom mi odovzdajte prostredníctvom mailu s predmetom [5EVL-2018] DU2-prog.

Bodovanie

Za úlohu je možné získať 15 bodov rozdelených medzi jednotlivé podúlohy. Samozrejme, je možné získať čiastočné body, či už za to, že ste išli s riešením správnym smerom, alebo preto, lebo vaše riešenie síce bolo správne, ale nebolo optimálne, teda nevyužilo najmenší počet vážení. Pri pojme najmenší nemyslím nutne úplne najmenší, ale skôr rádovo najmenší. Nesnažte sa teda optimalizovať váženia na pár vážení, hlavne nech to nie je o rád viac ako treba.

Čo môžete (ne)použiť pri riešení

Samozrejme, neodpisujte jeden od druhého! Kód, ktorý odovzdávate by mal byť váš. Naďalej platí, že ak ste zaseknutý, tak mi treba napísať. No a ako vždy, odporúčam to riešiť skôr ako večer pred deadlinom a poriadne si čítať zadanie. Okrem toho si kreslite, píšte a neprogramujte kým si to poriadne nerozmyslíte. Takisto by som povedal, že občas vám pomôže začať spisovať riešenie, ktoré máte. Lepšie si myšlienky sformulujete, keď ich naozaj spíšete.