Třetí série začátečnické kategorie třicátého sedmého ročníku KSP

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

Právě se díváte na leták třetí série 37. 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.

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 úloha37-Z3-1 Wi-Fi ve vlaku (8 bodů)

Kevin má za sebou rušný týden. Ve škole mu to dalo zabrat a doma neustále běží předvánoční úklid. Proto se tento týden více než kdy jindy těší na tu nejlepší část týdne – víkend, protože každý víkend jezdí vlakem za babičkou. Ve vlaku si hezky odpočine, koukne co se za týden objevilo na MyHroch – hrošiální síti pro hrochy a nechá svět kolem hezky utíkat, zatímco se blíží k babičce, která už na něj dychtivě čeká s roztopeným krbem a mističkou plnou cukroví.

Jak tak prochází skrz MyHroch, tak se mu nějak dlouho načítají příspěvky od Sáry, která je vášnivá a dobrá fotografka, proto má fotky v extra šťavnatém rozlišení. Když ale kouká na HrochRail Wi-Fi zdarma, tak kouká, že mu jeho HrochPhone ukazuje u Wi-Fi Vykřičníček – už zase jim blbne jednotka. HrochRail naštěstí už ukazuje u jednotek, jestli běží správně. Kevin se proto rozhodl nemeškat a přesadit se někam, kde všechny jednotky běží jako po másle, tudíž by se tam mohl podívat na Sářiny fotky Hroších vodopádů bez dlouhého čekání. Poraďte Kevinovi, kam si může sednout, aby na něj dosáhly pouze funkční Wi-Fi jednotky.

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 vstupu dostanete čísla R a J – počet řad ve vlaku a počet jednotek. Řady jsou číslované od 1 do R. Na dalších J řádcích vstupu dostanete specifikace každé jednotky v podobě r d f – řada ve které jednotka leží, dosah jednotky v řadách do obou stran, funkčnost buď 1, nebo 0. Dosah 1 znamená, že jednotka dosáhne na svou řadu a řady o 1 před ní a za ní.

Formát výstupu: Vypište jedno číslo – počet míst, kam dosahují jen dobré Wi-Fi jednotky. To znamená žádná špatná a alespoň jedna dobrá.

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

Praktická opendata úloha37-Z3-2 Řízky (10 bodů)

Když dnes Kevin dojel za babičkou, tak ho uvítala vřelým objetím. Kevin vždy rád jezdí za babičkou, protože ji má rád a je u ní klid a pohoda. Babička zase ráda vidí Kevina a váží si jeho společnosti, proto mu chce dnes udělat tu největší z radostí, které krom své hřejivé přítomnosti umí poskytnout – řízky. Avšak babička už ví, že Kevin má řízky natolik rád, že se spokojí jen s tím nejlepším. No jo, jenže jaký řízek je nejlepší? To je přece hrozně subjektivní. Babiččiny řízky jsou jistě nejlepší řízky, jenže který babiččin řízek je nejlepší z nich? To se přeci u Kevina každý týden mění! Jelikož je ale babička moc zkušená, tak už ví, jak na to. Každý řízek ohodnotila třemi vlastnostmi - macatost, šťavnatost a lahodnost.

Když se tohle Kevin dozvěděl, zachvátila ho hrdost na svou babičku. Tohle všechno, jen aby si její vnuk co nejvíce pochutnal. Tolik práce jen protože ho má babička tolik ráda a chce mu udělat radost. Teď už zbývá jen jediné, vybrat ten nejlepší. Ne, pět nejlepších! Babičce po těchto slovech naskočila slzička štěstí. S láskou teď pozoruje Kevina, jak si vybírá řízky a u toho se olizuje až za ušima. Buďte jako Kevin, navštivte babičku, udělejte babičce radost, stravte s ní hezké odpoledne a na oplátku možná také dostanete sadu ohodnocených řízků.

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.

Dostanete váhy tří vlastností řízků podle Kevinových aktuálních preferencí. Poté dostanete posloupnost ohodnocení těchto tří vlastností všech řízků. Vaším úkolem je (potom, co dáte babičce najevo, že jí máte rádi) určit 5 nejlepších řízků.

Formát vstupu: Na prvním řádku dostanete tři kladná čísla – M Š L – reprezentující aktuální váhy vlastností řízků. Na druhém řádku dostanete číslo Ř – počet řízků, které vám s láskou babička nasmažila. Na dalších Ř řádcích dostanete tři vlastnosti každého ze Ř řízků. i-tý řádek bude vypadat takto – mi ši li.

Formát výstupu: Ohodnocení každého řízku spočítáte podle jeho vah – M·mi + Š·ši + L·li. Vypište na samostatném řádku vlastnosti pět nejlepších řízků seřazených sestupně – od nejlepšího. Pokud babička navaří řízky se stejným ohodnocením, je jedno, v jakém pořadí budou mezi sebou.

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

Praktická opendata úloha37-Z3-3 Osmisměrka (12 bodů)

Kevin si s babičkou po obědě chtěli vyřešit osmisměrku, kterou babička dostává s Hroším oběžníkem. Babiččina osmisměrka je vždy složitá, ale Kevin ji řeší s radostí. Avšak tenhle měsíc to není tak jednoduché.

Do tiskárny se totiž poslaly osmisměrky od Skřítka a ten je vždycky trochu zákeřný. Skřítek si vymyslel, že vyrobí obrovskou osmisměrku, která bude mít stovky až tisíce slov na nalezení. Babička by však chtěla zjistit tajenku, která má speciální vánoční tematiku. Kevin by rád babičce pomohl, ale neví, jak na to. Pomůžete mu?

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.

Dostanete osmisměrku N × N a seznam slov, které v ní musíte najít. Vaším úkolem je v osmisměrce najít slova ze seznamu a vrátit zbývající znaky. Všechna slova ze seznamu se v osmisměrce nacházejí a můžou tam být i vícekrát. Dokonce se občas i překrývají.

Formát vstupu: Na prvním řádku dostanete dvě čísla: N – velikost osmisměrky (počet řádků a sloupců) a M – počet slov, která máte najít. Následujících N řádků tvoří samotnou osmisměrku, přičemž každý řádek obsahuje právě N znaků. Posledních M řádků obsahuje seznam slov, která se v osmisměrce skrývají.

Formát výstupu: Vypište na jeden řádek zbývající písmena po řádcích osmisměrky a na konci řádku z osmisměrky vypište mezeru. Kdyby nějaký řádek osmisměrky neobsahoval žádné zbývající písmeno, tak nevypisujte mezeru na konci řádku.

Ukázkový vstup: 
6 6
Hrocha
cedarg
sjedua
jxxe#r
rychly
.murou
murou
sjedu
agar
cedar
xx
#
Ukázkový výstup: 
Hroch je rychly .

Očekávaná časová složitost: O(N2 ·M)

Teoretická úloha37-Z3-4 Věšení ozdobiček (14 bodů)

Po zaslouženém odpočinku u osmisměrky se Kevin s babičkou dali do vánočních příprav. Takové vánoční přípravy u Kevinovy babičky, to je ale vážná věc. Kevinova babička totiž zve na vánoční večírek celý čtenářský spolek z Dolních i Horních Hrochovic, vše tak musí být řádně ozdobeno.

Babička se tedy letos rozhodla ověsit vánočními ozdobičkami velké okno v obývacím pokoji, u kterého její hosté tak rádi o Vánocích hrají deskové hry. Když ale Kevin pomohl snést ozdobičky z babiččiny půdy, všiml si, že se jich několik od minulého roku rozbilo a nebude tak možné jimi ověsit všechny háčky nad oknem. Rozhodl se ale, že se i tak pokusí rozvěsit ozdobičky na háčky co nejvíce rovnoměrně.

Nad oknem má babička v řadě H háčků na ozdoby. Pro každý háček na pozici i zná babička jeho vzdálenost hi od háčku na pozici i-1 (pro první háček máme h1 = 0). V krabici Kevin našel Z < H ozdob, které chce všechny rozvěsit na háčky tak, aby každé dvě ozdoby byly od sebe co nejdál. Formálněji řečeno se Kevin snaží nalézt takové rozvěšení ozdobiček na háčcích, že minimum ze vzdáleností mezi každými dvěma ozdobami je maximální možné.

Pomozte Kevinovi určit, na které háčky má dle výše popsaných pravidel zavěsit ozdobičky a na které ne.

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

Praktický kurz programování

Praktická opendata úloha

Pokud Tě lákají praktické úlohy, ale ještě neumíš žádný programovací jazyk, můžeš se podívat na náš Základní kurz programování, kde se můžeš naučit základy Pythonu: https://ksp.mff.cuni.cz/kurz/.

Zdrojáky praktických úloh

Praktická opendata úloha

Řešení praktických úloh může být ze začátku složité. Velmi často i nějaká triviální technická chyba ve zdrojovém kódu programu může znamenat, že program vrací špatný výsledek – a některé chyby se ze začátku špatně hledají. Proto Ti nabízíme možnost poslat zdrojový kód programu nějaké úlohy na adresu zdrojaky@ksp.mff.cuni.cz, kde se Ti pokusíme poradit. Do emailu prosím připiš:

Před termínem série Ti nemůžeme radit s algoritmem, ale pomůžeme s odladěním zdrojáku. Po termínu série pak můžeme poradit i s návrhem algoritmu – získáš tak znalosti do dalších sérií.