První série třicátého osmého ročníku KSP

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

Dostává se k vám první číslo hlavní kategorie 38. ročníku KSP.

Letos se můžete těšit v každé z pěti sérií hlavní kategorie na 4 normální úlohy, z toho alespoň jednu praktickou opendatovou. Dále na kuchařky obsahující nějaká zajímavá informatická témata, hodící se k úlohám dané série. Občas se nám také objeví bonusová X-ková úloha, za kterou lze získat X-kové body. Kromě toho bude součástí sérií seriál, jehož díly mohou vycházet samostatně.

Autorská řešení úloh budeme vystavovat hned po skončení série. Pokud nás pak při opravování napadnou nějaké komentáře k řešením od vás, zveřejníme je dodatečně.

Odměny & na Matfyz bez přijímaček

• Termín série: neděle 2. listopadu 2025 ve 32:00 (tedy další ráno v 8:00)
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Odznáček do profilu na webu si vyslouží ten, kdo z každé úlohy série získá alespoň 2 body.

Zadání úloh

• 38-1-1: One-shot burza
• 38-1-2: Bambulus
• 38-1-3: Mediánový poddaný
• 38-1-4: Jedno slovo
• 38-1-S: Seriál

38-1-1 One-shot burza (11 bodů)

Trpaslík Plesnivous se rozhodl, že drakův poklad je pro něj moc práce a musí si vydělat jinak. Jenže vydělávat standardní cestou je zaprvé náročné, zadruhé neefektivní a zatřetí nic pro něj. Proto se rozhodl jít za Lady Hrochtenzií – místním orákulem. Ta mu sdělila cenu uhlí pro každý z příštích N dní.

Bohužel si ale důlní úřad kontroluje velké finančně-uhelné transakce, proto smí Plesnivous za svých K sesterciů pouze jednou nakoupit libovolné kladné celé množství uhlí a jednou ho všechno prodat. Chce při tom postupovat se značnou obezřetností, aby si vydělal co nejvyšší sumu. Pomozte Plesnivousovi zjistit, kdy má uhlí nakoupit a kdy prodat, aby skončil s co nejvíce sestercii.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku dostanete N, počet dní, na které Lady Hrochtenzie předpověděla ceny uhlí, a K, Plesnivousův kapitál v sesterciích. Na druhém řádku dostanete N kladných celých čísel reprezentující ceny uhlí v daných dnech.

Formát výstupu: Na jednom řádku vypište dvě čísla – den, ve který má Plesnivous uhlí nakoupit a kdy prodat. Dny indexujeme jako správní trpaslíci od nuly. Pokud je takových řešení více, vypište libovolné z nich. Pokud Plesnivous na uhlí nemůže nic vydělat, nebo by dokonce prodělal, vypište namísto toho -1. Pozor, Plesnivousův výdělek se nemusí vejít do 32-bitového čísla.

8 6
3 7 2 4 9 1 5 4

5 6

Když by Plesnivous nakoupil v den 5, nakupoval by uhlí za 1 sestercius, tedy by jich mohl koupit 6. 6 uhlí potom v den 6 prodá každé za 5 sestercií, čímž získá peněžní obnos v hodnotě 6·5=30 sestercií. Vydělal tedy 30-6=24 sestercií, což je pro daný vstup maximální.

38-1-2 Bambulus (12 bodů)

Matúšovi se konečně podařilo rozjet jeho kariéru motivačního řečníka. O jeho sérii přednášek „Bambulus: tři pilíře životního štěstí?“ je nebývalý zájem a nezřídka bývají představení vyprodaná. Nově nabytá sláva s sebou však nese jistá úskalí: Matúšovi obdivovatelé se nemůžou shodnout na tom, který z pilířů jeho učení je nejdůležitější, a rozdělili se na tři navzájem rozhádané tábory. Jedni věří, že klíčem ke všemu je ladění (harmonie se sebou i okolím), druzí vidí hlavní smysl v řádění (následování svého vnitřního dítěte a žití v okamžiku), třetí nedají dopustit na parádění (hledání vnitřní i vnější krásy ve všedních věcech).

Tyto rozbroje jsou problém pro Matúšova vystoupení, jelikož příslušníci rozhádaných táborů si odmítají sednout vedle sebe. Po minulém představení, kde kvůli tomu zůstala půlka míst volná, už Matúšovi došla trpělivost. Přicházející diváci prostě dostanou nějaké místo přidělené, a basta. Jenže jak, aby byli pořád všichni spokojení, ale přitom volných míst zbylo co nejméně? Matúš je zaneprázdněn googlením motivačních citátů, a tak tento úkol připadl na vás.

Hlediště je tvořené N židlemi umístěnými v jedné řadě. Na začátku je hlediště prázdné a pak do něj po jednom přicházejí diváci. Vaším cílem je navrhnout algoritmus, který dostává události tvaru „právě přišel divák vyznávající 1./2./3. pilíř“ a na každou z nich odpovídá místem, na které si daný divák má sednout. Chceme přitom, aby vedle sebe nikdy neseděli dva diváci vyznávající různé pilíře.

Váš algoritmus je online: diváci přicházejí jeden po druhém, a nový divák přijde až potom, co umístíme předchozího. Již usazené diváky nejde přemisťovat.

Kvalitu vašeho řešení budeme hodnotit podle ztráty – množství volných míst, které zbývají v okamžiku, kdy už nejde umístit dalšího diváka. Stejně jako u časové složitosti nás zde nezajímá konkrétní číslo, ale pouze asymptotické chování: zdali je volných míst Θ(N), Θ(√N), nebo nějaká jiná funkce v N. Počet volných míst vyhodnocujeme na nejhorším možném vstupu. Můžete si představit, že před vchodem stojí Ríša, který Matúšovi nepřeje úspěch, a který dovnitř pouští diváky v takovém pořadí, aby váš algoritmus selhal co nejdříve. Ríša zná zdrojový kód vašeho algoritmu a má opravdu hodně času na vymýšlení co nejzapeklitějšího vstupu.

Příklad: Uvažme algoritmus, který každého přicházejícího diváka umístí na co nejlevější použitelné místo. Takový algoritmus nechá až N/2 míst volných, a to v situaci, kdy se nám přicházejí střídavě vyznavači 1. a 2. pilíře – pak budou na sudých místech sedět diváci a lichá místa budou prázdná. Naopak si jde rozmyslet, že více než N/2 volných míst nikdy nezůstane. Ztráta tohoto algoritmu je tedy Θ(N).

Cílíme na algoritmus, který v nejhorším případě ponechá Θ(log N) míst volných, ale částečné body získáte i za asymptoticky horší závislost na N (třeba Θ(√N)). Ve vašem řešení nezapomeňte zdůvodnit, proč je jeho ztráta zrovna taková, jaká tvrdíte.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

38-1-3 Mediánový poddaný (14 bodů)

Za sedmero horami a sedmero řekami vládl moudrý král Ríša. Ten si udržoval svoje rádce, kteří mu každoročně počítali a plánovali chod království. Nicméně aby rádci mohli připravit své plány, potřebovali by sehnat reprezentativního poddaného…

Ríšovo království je rozděleno na K krajů. Protože Ríša má rád pravidelnost, v každém kraji je právě N poddaných, kde každý poddaný má unikátní celočíselnou pracovitost P_i (1 ≤ P_i ≤ P_max). Rádci by chtěli sehnat poddaného, pro něhož se počty poddaných s vyšší pracovitostí a s nižší liší nejvýš o 1. Tedy poddaného, který je mediánem všech poddaných v celém království.

Nicméně Ríšovo království je velmi velké a rozlehlé, takže se záznamy o pracovitosti poddaných udržují pouze v krajích, kde žijí. Ríša ale může vyslat svého věrného posla s konstantně (Konstantně dlouhá zpráva smí obsahovat jen konstantně mnoho „rozumně velkých“ čísel – čísel velkých nejvýše polynomiálně k číslům na vstupu. Délka zprávy v bitech tedy musí být v O(log K + log N + log P_max).) dlouhým rozkazem do jednoho z krajů. Tam může zkonzultovat archivy a vrátit se s konstantně dlouhým výsledkem. Mezi vysláním posla a jeho návratem uplyne vždy jeden týden. Na základě všech předchozích výsledků může poté Ríša posla vyslat do dalšího kraje.

Například můžeme poslat posla:

• Zjistit nejmenší pracovitost v daném kraji.
• Zjistit počet poddaných s pracovitostmi mezi A a B.

Ale nemůžeme:

• Vyslat ho se seznamem největších pracovitostí v každém kraji, neboť rozkaz je dlouhý Θ(K).
• Nechat si poslat seznam N/2 nejméně pracovitých poddanných v kraji, neboť výsledek je dlouhý Θ(N).

Pomozte Ríšovi zjistit medián pracovitosti. Vaše řešení budou hodnocena primárně podle celkového počtu vyslání Ríšova věrného posla. Při návrhu algoritmu předpokládejte, že K je řádově menší než N, a to je řádově menší než P_max.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

38-1-4 Jedno slovo (8 bodů)

Kevinovi přišla s novou sérií od orgů KSP i nějaká podivně vypadající zpráva… a kdyby jen jedna!

Všiml si, že každý vstup obsahuje na prvním řádku číslo vstupu, zbytku ale nerozumí a potřebuje vaši pomoc.

Nalezněte řešení.

Rada: pokud jste ještě nikdy neluštili šifry, může se vám hodit přečíst si třeba začátek tohoto návodu, po část „Kódování znaků“. Nehledejte však v řešení veliké složitosti, orgové KSP jsou především informatici a spíš než vlajková abeceda je zajímají způsoby kódování, které s informatikou přirozeně souvisejí.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

38-1-S Seriál (15 bodů)

Vážení řešitelé, na letošní seriál si budete muset ještě chvíli počkat. Avšak čekání jistě bude stát za to.