Pátá série začátečnické kategorie třicátého čtvrtého ročníku KSP

Právě se díváte na leták páté série 34. ročníku KSP-Z, neboli Korespondenčního Semináře z Programování, Začátečnické kategorie. Zapojit se může každý středoškolák i základoškolák, řešit můžete začít i v případě, kdy jste se nezúčastnili prvních čtyř sérií.

Letos bude v KSP-Z pět sérií po čtyřech úlohách za celkem 220 bodů. Pokud budete mít jakoukoliv otázku, neváhejte se zeptat. Kontaktní adresy najdete v patičce na konci letáku. Přejeme hodně štěstí!

Zadání úloh


Praktická opendata úloha34-Z5-1 Splitwise (8 bodů)


Kevin má ve třídě několik kamarádů, se kterými během roku podnikal spoustu výletů. Protože někdy bylo potřeba zaplatit hromadně nebo někomu půjčit peníze, když si zapomněl peněženku, Kevin během celého roku zapisoval, kdo za koho platil.

Nyní se ale blíží konec roku a kamarádi si do prázdnin nechtějí nic dlužit. Kevin tedy potřebuje pro každého ze svých kamarádů spočítat, kolik peněz dluží nebo by naopak měl dostat. Protože je ale záznamů hodně, bojí se, že kdyby vše počítal sám, udělal by v počtech chybu. Rád by si tedy pomohl nějakým programem.

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 je n – počet záznamů o útratách. Každý z dalších n řádků přestavuje jeden záznam, který se skládá z:

Celková částka je vždy dělitelná počtem kamarádů.

Formát výstupu: V libovolném pořadí vypište na výstup seznam kamarádů a jejich bilancí tak, aby se v něm každý kamarád objevil právě jednou. Pokud daný kamarád dluží, jeho částka bude záporná, pokud by měl dostat zaplaceno, pak kladná.

Ukázkový vstup:
2
800 Adam 4 Adam Beda Cyril Erik
200 Cyril 1 Adam
Ukázkový výstup:
Adam 400
Beda -200
Cyril 0
Erik -200

Řešení


Praktická opendata úloha34-Z5-2 Otáčení papíru (11 bodů)


Škola, kterou navštěvuje Kevin a Sára, si postavila parkoviště pro učitele a zabezpečila jej automatickou závorou a kamerou, která čte poznávací značky. Ještě téhož dne se Kevin dočetl, že firmware obsahuje mnoho chyb a že při přečtení některých jednopísmenných poznávacích značek zahraje dětskou melodii.

Sára by to ráda vyzkoušela, ale protože nechce být vidět na záznamech z kamery, hází raději z okna papíry s malým písmenem b. Fixa se propila i na druhou stranu papíru, tedy z obou stran papíru je vidět nějaké písmeno. Venku ale fouká vítr a tak se papír všemožně otáčí. Poradíte Sáře, jak se její písmeno přečte?

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 počet hodů n. Na každém z následujících n řádků je řetězec složený ze znaků R, L, H a V. Ten říká, jak se postupně v důsledku působení větru papír otáčel.

Směry os jsou udávány vzhledem k zemi a při otáčení papíru se nemění. Jednou tedy může horizontální osa být ta delší, jindy zase ta kratší.

Formát výstupu: Za každý hod vypište na výstup b, d, p, nebo q, pokud bylo takto původní b čitelné, nebo ?, pokud nevypadalo jako ani jedno z uvedených. Výstupní řádky uveďte ve stejném pořadí, jako jsou hody zadány na vstupu.

Ukázkový vstup:
3
RLLLHLLVHLL
HHVHVLLVHVV
RRHRHRHRHHV
Ukázkový výstup:
p
p
?

Řešení


Praktická opendata úloha34-Z5-3 Počet nových mostů (11 bodů)


Kevin se rozhodl jet se svojí třídou pomoct do zoo na Hroším jezeru. Bohužel jezero s ostrovy před nedávnem zasáhly obrovské záplavy a některé mosty se z náporu vody zbortily. Pro návštěvníky a ošetřovatele je velmi důležité, aby se mohli dostat suchou nohou z každého ostrova na ostatní.

Je tedy potřeba postavit nové mosty (každý most spojuje dvojici ostrovů). Aby byly hotové co nejrychleji, Kevin se nabídl, že zjistí, jakým nejmenším počtem mostů je možné všechny ostrovy propojit.

Kevin dostal od majitele seznam ostrovů a mostů, které stojí. Jeho úkolem je spočítat, kolik nových mostů je potřeba postavit.

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 dvě čísla n a k. První říká, kolik je na jezeře ostrovů, a druhé, kolik mostů přežilo povodeň. Na dalších k řádcích je vždy dvojice čísel ostrovů, které představují konce jednoho mostu. Ostrovy jsou očíslované od 0 do n-1.

Formát výstupu: Na výstup vypište jediné číslo představující počet mostů, které je potřeba postavit.

Ukázkový vstup:
17 14
0 1
0 2
0 3
0 4
8 5
8 7
8 6
12 10
11 12
9 11
13 14
14 15
15 16
16 13
Ukázkový výstup:
3

Řešení


Teoretická úloha34-Z5-4 Tajemná ohrada (14 bodů)


Na náměstí vyrostla veliká ohrada. Kevin s Petrem jsou zvědaví, co je uvnitř, ale ohrada je vysoká a neprůhledná. Tak se předhánějí, kdo vymyslí větší bláznivost, která by se v ní mohla skrývat. Kevin zrovna navrhl, že tam bude schovaný desetihlavý drak, kterému se udělalo špatně po vyjedení školní jídelny. Petr oponuje, že ten by se tam určitě nevešel.

Hádali by se dodnes, kdyby kolem neprošla Sára a nenavrhla, ať spočítají obsah plochy obehnané ohradou. Jde to snadno, jelikož ohrada má všechny úhly pravé. Stačí ji tedy obejít, počítat při tom kroky a zapisovat si: dva na sever, tři na východ, jeden jižně, ….

Navrhněte algoritmus, který podle zaznamenaných kroků spočitá obsah plochy ve čtverečních krocích. Snažte se o co nejlepší časovou složitost vzhledem k délce záznamu kroků. Můžete předpokládat, že posloupnost kroků končí na tom místě ohrady, kde začala, a že ohrada nikde neprotíná samu sebe.

Příklad: Vstupu 2S 3V 1J 1V 3J 3Z 1S 1V 1S 2Z odpovídá následující ohrada, která ohraničuje prostranství o ploše 12 čtverečních kroků.

Ukázka ohrady

Řešení