Druhá série třicátého čtvrtého ročníku KSP

Dostává se k vám druhé číslo hlavní kategorie 34. ročníku KSP.

Opět se můžete těsit několik praktických i teoretických úloh, speciálně bychom vás chtěli upozornit na jednu kompetitivní úlohu s procházkou po Brně. V této sérii se také objeví pokračování Manimového seriálu, ale jeho zadání bude dostupné až po ukončení minulé série.

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

Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek. Úspěšným řešitelem se stává ten, kdo získá za celý ročník (této kategorie) alespoň 50% bodů. Za letošní rok půjde získat maximálně 300 bodů, takže hranice pro úspěšné řešitele je 150. Maturanti pozor, pokud chcete prominutí využít letos, musíte to stihnout do konce čtvrté série, pátá už bude moc pozdě. Také každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů, darujeme KSP propisku, blok, nálepku na notebook a možná i další překvapení.

Zadání úloh


Praktická opendata úloha34-2-1 Skupinová jízdenka (9 bodů)


Alice a Bob plánují navštívit Carol. Alice bydlí v Adršpachu, Bob v Břeclavi a Carol v Chebu. Alice i Bob chtějí jet vlakem firmy HippoExpres, která právě vyhlásila slevu na skupinové jízdné. Proto se jim vyplácí sejít se v nějakém městě po cestě a odtamtud už jet společně.

Vymyslete algoritmus, který jim cestu naplánuje. Dostanete mapu železniční sítě: neorientovaný graf, jehož vrcholy jsou stanice a hrany tratě mezi nimi, ohodnocené vzdálenostmi v kilometrech. Dále dostanete cenu jednotlivého i skupinového jízdného v korunách za kilometr. Zjistěte, kde se mají Alice s Bobem sejít, aby je cesta stála co nejméně.

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: První řádek vstupu obsahuje 4 celá čísla: počet stanic n, počet tratí m, cenu jednotlivého jízdného v Kč za km, cenu skupinového jízdného v Kč za km. Následujících m řádků popisuje jednotlivé trati. Na každém z nich jsou 3 celá čísla: koncové stanice trati a délka trati v kilometrech. Stanice číslujeme od 1 do n, číslo 1 je Adršpach, 2 Břeclav a 3 je Cheb.

Formát výstupu: Vypište jediné číslo: nejmenší možnou cenu, kterou Alice s Bobem dohromady zaplatí za jízdenky.

Ukázkový vstup:
4 5 1 1
1 4 3
2 4 3
3 4 3
1 3 5
2 3 5
Ukázkový výstup:
9

Teoretická úloha34-2-2 Lezení (10 bodů)


Sportovní lezení na olympijských hrách sestává ze tří disciplín: lezení na rychlost, bouldering a lezení na obtížnost. Počet trestných bodů, které lezec dostane za disciplínu, odpovídá jeho pořadí (počítáno od 1). Celkový počet trestných bodů je součin trestných bodů za jednotlivé disciplíny. Vítězem se stává lezec, který má nejmenší počet celkových trestných bodů, podobným způsobem se seřadí zbylí lezci.

Například pokud by lezec A skončil v disciplínách na 1., 4. a 7. místě a lezec B na 2., 13. a 1. místě, pak dostane lezec A celkem 1 ·4 ·7 = 28 trestných bodů a umístí se tak až za lezcem B s 2 ·13 ·1 = 26 trestnými body.

První dvě disciplíny již proběhly a je známé pořadí všech n lezců v obou dvou disciplínách. Náš nejlepší lezec je mistrem v lezení na obtížnost a věří si na první místo v této disciplíně. I tak ale netuší, jaké bude výsledné pořadí. Pomůžete mu zjistit, na jaké nejhorší příčce se může umístit, pokud by se mu skutečně podařilo skončit první v lezení na obtížnost, ale ostatní by se mohli v lezení na obtížnost seřadit libovolně?

Ilustrace: Hroch

Teoretická úloha34-2-3 Na Hroších pláních (12 bodů)


Na Hroších pláních byla objevena obrovská naleziště čokolády! Všichni organizátoři KSPčka se tam hned rozjeli, aby si každý z nich vykolíkoval svůj claim – území, kde bude těžit.

Každý claim má tvar n-úhelníku v rovině (ne nutně konvexního). V jeho vrcholech jsou zapíchané kolíky, po obvodu očíslované postupně od 1 do n. Každý organizátor má svou barvu kolíků, ale i tak je proklatě obtížné zjistit, jestli se nějaké dva claimy protínají. Vymyslete algoritmus, který to pozná.

Vymyslete algoritmus, který na vstupu dostane souřadnice kolíků určujících dva n-úhelníky claimů. Na výstup vypíše buď souřadnice nějakého bodu ležícího v průniku obou claimů, nebo sdělí, že claimy žádný společný bod nemají. Pokud se dva claimy jenom dotknou (vrcholem nebo hranou), za průnik to nepovažujeme.

Lehčí variantaLehčí varianta (za 8 bodů): Vyřešte případ, kdy oba n-úhelníky jsou konvexní.


Praktická opendata úloha34-2-4 Brněnská procházka (14 bodů)


Kevin chce zorganizovat dlouhou procházku po Brně a okolí, ale nechce se zbytečně dívat na stejná místa vícekrát. Proto se rozhodl, že zvolí poněkud netradiční omezení na trasu procházky.

Brno je ohodnoceným neorientovaným grafem, kde vrcholy odpovídají křižovatkám a hrany ulicím. Ulice jsou celočíselně ohodnoceny jejich délkou v metrech. Vaším úkolem je najít co nejdelší cestu, ze které nezahlédnete žádnou jinou ulici dvakrát (tedy pokud vezmete libovolné dva vrcholy cesty, které po sobě těsně nenásledují, tak jejich vzdálenost v grafu bude alespoň dva). Začít i skončit můžete na libovolném vrcholu, jen od sebe také musí udržet vzdálenost dva. Nejdelší cesta je ta, která má největší součet délek hran, na počtu hran Kevinovi nezáleží.

Toto je speciální soutěžní úloha se statických vstupem, kde všichni řešitelé dostanou stejný vstup a přes Odevzdávátko pak odevzdají nejlepší řešení, které se jim povede najít. Obodování úlohy provedeme až po konci série a to tak, že nejlepší řešení dostane plný počet bodů a ostatní řešení dostanou body odstupňovaně podle toho, jak byla dobrá. Zároveň slibujeme, že každé korektní řešení dostane alespoň jeden bod.

V průběhu série se můžete s ostatními porovnávat pomocí průběžné online výsledkovky. Upozorňujeme, že se v ní mohou vyskytnout i řešení od organizátorů.

Vizualizace vstupu

Jde o těžkou úlohu, pro kterou neslibujeme existenci efektivního algoritmu na nalezení optimálního řešení. Pro inspiraci, jak k této úloze přistoupit, se můžete podívat na vzorová řešení minulé soutěžní úlohy 33-3-4. Vezměte ale na vědomí, že jde o výrazně odlišnou úlohu, a tak budete muset zvolit jiný přístup a rozhodně se vám vyplatí experimentovat.

Tuto úlohu také doporučujeme začít řešit včas, vstupní data jsou relativně velká a bude se vám velmi hodit čas na postupné vylepšování vašeho řešení.

Formát vstupu: Na prvním řádku dostanete počet vrcholů N a počet ulic M. Následuje N řádků s definicemi vrcholů ve formátu v lat lon, kde v je číslo vrcholu a latlon popisují GPS souřadnice – ty se mohou hodit pro vizualizace, ale nijak je není potřeba použít pro počítání délek. Vstup zakončuje M řádků s definicemi hran. Na každém řádku je popsána jedna hrana trojicí čísel oddělenou mezerami: v1, v2D. Taková hrana spojuje vrcholy v1v2 a má celočíselnou délku D metrů. Vrcholy jsou indexované od nuly.

Formát výstupu: Na první řádek vypište celkovou délku nalezené cesty v metrech. Poté vypište čísla vrcholů v pořadí, ve kterém je cesta navštěvuje, každé na samostatný řádek.

Odevzdávátko spočítá délku cesty a přidá odevzdané řešení do průběžné výsledkovky. Upozorňujeme, že od každého řešitele bereme v potaz vždy jeho poslední odevzdané řešení, i kdyby si tím měl zhoršit skóre. Proto vám doporučujeme si svá řešení ukládat, abyste je případně mohli odevzdat znovu.

Zdroje: Graf k této úloze jsme získali zpracováním dat z projektu OpenStreetMap.

Ukázkový vstup:
6 7
0 49.16298 16.56755
1 49.16316 16.56767
2 49.16319 16.56854
3 49.16328 16.56858
4 49.16328 16.56951
5 49.17429 16.55060
0 2 15
0 4 10
1 2 5
1 3 20
2 5 1
3 4 5
3 5 2
Ukázkový výstup:
40
3
1
2
0

Teoretická úloha34-2-X1 Převod čísel (10 bodů)


Kevin začal řešit úkol do informatiky. Chtěli po něm, aby převáděl čísla mezi desítkovou a dvojkovou soustavou. Ale tento úkol ho po chvíli přestal bavit, a tak začal převádět čísla i mezi jinými soustavami. Vaším úkolem bude mu s těmito převody pomoct. Vymyslete program, který bude převádět čísla ze soustavy o základu A do soustavy o základu B.

Na vstupu dostanete nejprve dvojici čísel A a B následovanou N čísly mezi 0A-1 značící vstupní číslo v soustavě o základu A. Výstupem vašeho programu bude posloupnost čísel mezi 0B-1 reprezentující totéž číslo, ale v soustavě o základu B.

Ve vašem programu ovšem nemůžete pracovat s libovolně velkými čísly v konstantním čase. Nemůžete tedy převést číslo na vstupu do jednoho čísla a to pak dále převádět do výstupní soustavy. Můžete ale předpokládat, že v konstantním čase umíte pracovat v čísly velikosti O((A+B)k) pro nějakou pevnou konstantu k.

Nápověda: Existují algoritmy, které násobí n-ciferná čísla s časovou složitostí O(nc) pro 1≤ c<2. Najdete je například v Průvodci labyrintem algoritmů v kapitole Rozděl a panuj. Ve svém řešení můžete takový algoritmus používat jako podprogram, aniž byste ho museli sami popisovat.


Seriálová úloha34-2-S Seriál (15 bodů)


Druhý díl seriálu bude vydán až po skončení prvního dílu na začátku prosince