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

Celý leták v PDF.

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

Letos (jako obvykle) 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 občas na kuchařky obsahující nějaká zajímavá informatická témata, hodící se k úlohám dané série. 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 25. října 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.

Zadání úloh

• 39-1-1: Počet podposloupností KSP
• 39-1-2: Oboustranně nejbližší hnízdo
• 39-1-3: Vysílač
• 39-1-4: Sněhuláci
• 39-1-S: Seriál

39-1-1 Počet podposloupností KSP (10 bodů)

Kevin se po horkém létě konečně dostal k letáku zadání 1. série KSP. Když si ho tak ve stínu četl, všiml si, že se v něm často opakují písmenka K, S, P. To ho uvedlo do počítacího tranzu – kolikrát se v letáku vyskytuje řetězec KSP jako podposloupnost?

Pomozte Kevinovi s počítáním. Dostanete řetězec znaků. Vaším úkolem bude spočítat, kolikrát se slovo KSP vyskytuje v daném řetězci jako podposloupnost. KSP je podposloupnost řetězce, pokud se v něm nachází K, potom někdy později S a po něm někdy P. Například tedy KSP je podposloupností řetězce KASIOPEA.

Možná se vám bude hodit přečíst si naši základní kuchařku, zejména kapitolu Předpočítané mezivýsledky.

Formát vstupu: Na vstupu dostanete jeden řádek s řetězcem z velkých písmen anglické abecedy.

Formát výstupu: Vypište jedno číslo – počet, kolikrát se KSP vyskytuje v daném řetězci jako podposloupnost. Slibujeme, že výsledek se vejde do 64-bitového čísla, do 32-bitového už se ale vejít nemusí. Pokud programujete v Pythonu, nemusí vás to trápit, ale např. v Céčku budete potřebovat long long int.

KKSSKSP

7

Slovo KSP v daném řetězci najdeme jako podposloupnosti K_S___P, K__S__P, K____SP, _KS___P, _K_S__P, _K___SP, ____KSP.

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.

39-1-2 Oboustranně nejbližší hnízdo (11 bodů)

To se takhle Ríša potuloval v Bostonu, na svém dobrodružství za krocením orlů. U místního YMCA se zeptal svého spirituálního průvodce v podobě kamenného obličeje vytesaného do stěny, kde ve městě se nachází hnízda divokých orlů. No to je náhodička, že je to na každé křižovatce kromě té, na které zrovna stojí!

Ríša ale ví, že souboj s orlem bude lítý a únavný, proto chce šetřit své síly. A to jak při cestě k hnízdu, tak zpátky do YMCA. Proto by ho zajímalo, ke kterému orlímu hnízdu se má skrz spletitou síť bostonských jednosměrek vydat, aby mu cesta tam i zpět zabrala co nejméně času.

Ríša vás potřebuje. Nachází se u YMCA a neví kam dál. Pomozte mu najít hnízdo, pro které je součet délek nejkratší cesty tam a cesty zpátky nejmenší. Pokud je takových hnízd více, vyberte to na křižovatce s nejnižším číslem.

Může se vám bude hodit přečíst si naši kuchařku o grafech.

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 jsou čísla N a M značící počet křižovatek a ulic.

Na dalších M řádcích jsou vždy dvě čísla u_i, v_i značící, že z křižovatky u_i do křižovatky v_i vede jednosměrná ulice. Křižovatky číslujeme od nuly.

Ríša stojí na křižovatce 0. Na všech křižovatkách kromě té jeho se nachází orlí hnízdo.

Formát výstupu: Na jediném řádku vypište dvě čísla: délku nejkratší možné výpravy z YMCA přes orlí hnízdo zpět do YMCA, a číslo orlího hnízda, které při ní navštívíme. Existuje-li více nejkratších výprav, zajímá nás ta s orlím hnízdem s co nejnižším číslem křižovatky. Slibujeme, že řešení existuje. Kromě toho o bostonské silniční síti nic neslibujeme, například neslibujeme, že se z každé křižovatky dá dostat na každou jinou.

5 8
0 1
0 2
1 2
2 4
3 4
4 0
4 1
4 3

3 2

Na křižovatku 2 se dá dostat cestou 0 →2 a z ní se zpátky do YMCA dá dostat cestou 2 →4 →0. Celkem tedy Ríša projde třemi ulicemi. Výprava kratší délky neexistuje a jediná další výprava délky tři je do orlího hnízda na křižovatce 4.

39-1-3 Vysílač (10 bodů)

Kocourkovský Starosta Petříček se rozhodl obyvatelům svého městečka zlepšit život. A co by lidem udělalo větší radost než rychlejší internet? Ono se to jednoduše zlepšuje, když počáteční množství vysílačů je nula. Protože však doteď žádný signál neměli, chtějí mít všichni vysílač co nejblíže k sobě.

Pomozte starostovi Petříčkovi umístit vysílač co nejférověji. Síla signálu pro jeden dům slábne s druhou mocninou euklidovské vzdálenosti od vysílače. Vymyslete, kam vysílač umístit, aby byl součet druhých mocnin euklidovských vzdáleností od vysílače ke každé budově co nejnižší.

Euklidovská vzdálenost je odvozena z Pythagorovy věty. Podívejte se na následující obrázek:

Na vstupu dostanete souřadnice N bodů v rovině reprezentujících domy Kocourkova. Vašim úkolem je zjistit, kam vysílač umístit. Důležité je také dokázat, že je vaše řešení správné.

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

39-1-4 Sněhuláci (14 bodů)

Přichází podzim a Kevin moc dobře ví, co to znamená. Hbitě si nasazuje své pracovní kalhoty, gumáky a rukavice. Nikdo ho dnes nemůže zastavit. Je čas házet po kamarádech koule z bláta.

Jenže Sáře, Petrovi ani Honzovi se to z nějakého nepochopitelného důvodu nelíbí. Jenže jak zastavit Kevina, který si už na ně připravil nesčetně blátových koulí? Musí být vynalézaví. Proto Kevina přesvědčí, aby s municí udělal něco lepšího – aby ze svých koulí stavěl sněhuláky.

Pro ty nezasvěcené z vás: takový sněhulák se staví z jedné až tří různě velikých koulí. Kevinovi se nápad zprvu moc líbil, jenže pak si uvědomil, jak to jeho kamarádi mysleli. Rozhodl se proto na protest postavit sněhuláků co nejméně.

Pomozte Kevinovi vymyslet, do jakých skupin koule uspořádat, aby vzniklo sněhuláků co nejméně. Na vstupu dostanete seznam velikostí N Kevinových koulí – označme je k₁, …, k_N. Velikosti se mohou libovolně opakovat, avšak pro všechna i platí, že 1≤ k_i≤ 10N. Vymyslete algoritmus, který koule uspořádá do skupin po jedné až třech různě velkých koulích, aby bylo výsledných skupin co nejméně.

Poznámka: Jako vždy je hlavním kritériem hodnocení algoritmu jeho správnost. U této úlohy si doporučujeme opravdu důkladně rozmyslet, že vaše řešení funguje ve všech případech, i těch okrajových. Nezapomeňte důkaz správnosti zahrnout do řešení.

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

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

I letošním ročníkem vás bude provázet seriál. V každé sérii se objeví jeden díl, který bude obsahovat nějaké povídání a navíc úkoly. Za úkoly budete moci získávat body podobně jako za klasické úlohy série.

První díl seriálu se zde za nějakou chvíli objeví.