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

Celý leták v PDF.

Nový školní rok je tady, a s ním přichází i nový ročník KSP-Z! Začátky mohou být někdy náročné, a proto jsme tu, abychom vám pomohli. Pokud narazíte na jakýkoliv problém, neváhejte nám napsat na e-mail zdrojaky@ksp.mff.cuni.cz. Odpovíme vám co nejdříve. Pokud byste měli potíže s načítáním vstupů pro naše úlohy, tak jsme připravili návod v naší encyklopedii, který vám s tím pomůže.

Kevin a Sára se letos rozhodli objevovat různé kouty světa. Jejich první zastávkou je Itálie, kam chtějí vyrazit za kulturou, ale jako obvykle narazí na několik problémů. Pomůžete jim s jejich řešením a tak zajistit, aby jejich dovolená byla co nejlepší?

Právě se díváte na webový leták první série 39. 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.

V průběhu roku vydáme několik dalších sérií úloh podobných této. Pokud budete mít jakoukoliv otázku, neváhejte se zeptat. Kontaktní adresy najdete v patičce webu. Přejeme hodně štěstí!

Zadání úloh

Praktická opendata úloha39-Z1-1 Neapolská opera (8 bodů)

Kevin a Sára odjeli na dovolenou do Neapole a rozhodli se, že zajdou do opery. Zjistili, že se tam koná několik představení najednou, a chtějí si vybrat ta nejlepší. Každou operu si ohodnotili podle toho, jak moc je zaujal její název a recenze. Nyní chtějí vybrat takovou kombinaci představení, aby měli co největší zážitek. Pro každou operu tak znají spokojenost, kterou by jim její zhlédnutí přineslo. Pomůžete jim vybrat takovou kombinaci představení, aby jejich celková spokojenost byla co nejvyšší?

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.

Opery začínají v přesných časových slotech, kterých je N. Každý slot obsahuje M představení, z nichž si Kevin a Sára musejí vybrat právě jedno. Vaším úkolem je zjistit, jaká je nejvyšší spokojenost, které mohou Kevin a Sára dosáhnout, pokud navštíví právě jedno představení z každého slotu.

Formát vstupu: Na prvním řádku vstupu dostanete čísla N, M označující počet slotů a počet představení v každém slotu. Na dalších N řádcích vstupu se nachází popis jednotlivých slotů. Slot popisuje M čísel, kde každé číslo vyjadřuje spokojenost, kterou by Kevin a Sára měli z daného představení. Spokojenost je vždy celé číslo v rozmezí od -100 do 100.

Formát výstupu: Vypište maximální celkovou spokojenost, které mohou Kevin a Sára dosáhnout, pokud se zúčastní právě jednoho představení z každého slotu.

Ukázkový vstup: 
3 4
10 25 -5 18
-3 -10 -5 -2
80 12 40 95
Ukázkový výstup: 
118

Celková spokojenost Kevina a Sáry je 25 + (-2) + 80. Všimněte si, že ve druhém slotu přinášejí všechna představení zápornou spokojenost, ale Kevin se Sárou stejně na nějaké z nich musejí jít.

Praktická opendata úloha39-Z1-2 Sicilská vražda (10 bodů)

V malinké vesničce na Sicílii, zvané Meziklasí, je obvykle naprostý klid. Všichni žijí šťastný a bezstarostný život. Nikdy by nikoho ani nenapadlo, že by se zde mohlo něco přihodit… Dnes se ale na kraji lesní stezky našlo tělo s několika bodnými ranami. Jistě se jednalo o vraždu, tohle se nestalo náhodou. Nikdo tomu nemůže uvěřit. Vražda? V Meziklasí? To přece není možné, sicilská mafie dorazila do našeho zapadákova! Ve vesnici nastal chaos. Všichni se bojí vycházet. Bojí se s kýmkoliv mluvit. Nikdo nikomu nevěří.

Statečný Kevin se však rozhodl, že tomu přijde na kloub a vraha vypátrá. Je si jistý, že obyvatelé Meziklasí by mu nikdy nelhali. To ale určitě neplatí pro našeho vraha. Vrazi přece zásadně zapírají a nikdy nic nepřiznají. Kevin se tedy vydá všechny vyslechnout.

Po svém vyšetřování si všechny výpovědi srovná a najde tu lživou. Lživou výpověď pozná tak, že se odpověď na danou otázku liší od ostatních odpovědí na tutéž otázku. Aby si jednotlivé výpovědi mohl porovnávat, vždy stejnou otázku položí na alespoň dvou různých výsleších. Může se ale stát, že ačkoliv se budou některé odpovědi lišit, nebude jisté, která z nich je ta lživá. V takovém případě Kevin uzná, že případ je nad jeho síly a předá svou práci někomu kvalifikovanějšímu. Také je možné, že se všechny výpovědi na tytéž otázky budou shodovat. To znamená jediné: vrah už se stihl z Meziklasí vypařit.

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 číslo N – počet otázek u jednotlivých výpovědí. Otázky jsou číslovány od 0 do N - 1. Na dalších N řádcích vstupu dostanete jednotlivé otázky v podobě q=a  – otázka = odpověď.

Formát výstupu: Vypište ANO i-tý řádek vraha, pokud se našel jistý vrah, NE, když vrah jistý není, a UNIKL, pokud se vrah z Meziklasí vypařil.

Ukázkový vstup: 
9
nuz=krvavy
holub=na_strese
kocka=cerna
kocka=cerna
holub=na_strese
kocka=cerna
nuz=cisty
nuz=krvavy
kocka=cerna
Ukázkový výstup: 
ANO 6

Praktická opendata úloha39-Z1-3 Kevin v Itálii (12 bodů)

Kevin jel na dovolenou do Itálie a rozhodl se cestovat veřejnou dopravou. Nastoupil do autobusu a chtěl dojet až na konečnou. Jenže na předposlední zastávce ho řidič bez pardonu vyhodil – autobus sice na konečnou jede, ale již bez cestujících (prostě blázniví Italové…).

Pomůžete Kevinovi zjistit, zda se dokáže dostat ze stanice A do stanice B pomocí těchto poněkud šílených spojů?

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.

K dispozici máte síť autobusových linek. Každá linka je jednosměrná a zastavuje na posloupnosti zastávek. Do své konečné zastávky však nikdy neveze cestující (všichni musejí vystoupit nejpozději na předposlední zastávce). Vaším úkolem je pro zadané dvojice stanic určit, zda existuje způsob, jak se dostat ze stanice A do stanice B jako platící pasažér.

Formát vstupu: Na prvním řádku vstupu dostanete čísla N a Q, která značí počet autobusových linek a počet dotazů. Následuje N řádků popisujících jednotlivé autobusové linky. Popis linky se skládá z nezáporných čísel zastávek a1, a2, …, ak, na kterých linka zastavuje. Každá linka má alespoň dvě zastávky. Následujících Q řádků obsahuje dotazy. Každý dotaz tvoří dvě čísla A a B označující výchozí a cílovou zastávku.

Formát výstupu: Pro každý z Q dotazů vypište na samostatný řádek ANO, pokud se lze ze zastávky A do B legálně dopravit, jinak vypište NE.

Ukázkový vstup: 
5 2
3 6 4 2 7
5 8 2
1 3 6 4 5
5 2 7
1 7 4 3 8 5
1 2
1 5
Ukázkový výstup: 
ANO
NE

Když použijete rekurzivní řešení, tak v Pythonu se vám může hodit navýšit limit rekurze. Pro jeho navýšení stačí na začátek napsat:
import sys; sys.setrecursionlimit(100000).

Teoretická úloha39-Z1-4 Záchrana Italské MHD (14 bodů)

Sára se rozhodla zjistit, proč autobusy v Itálii vlastně nefungují správně. Zjistila, že dvě ze čtyř společností provozujících autobusovou dopravu vyhlásily bankrot. Zbylé dvě společnosti si nyní musejí rozdělit jejich trasy. Antimonopolní úřad jim však dal přísnou podmínku: žádná dvě sousední města (mezi kterými vedou trasy) nesmějí být obsluhována stejnou společností.

Jakkoli se však provozovatelé snažili, města se jim podle tohoto pravidla rozdělit nedařilo. Pomůžete Sáře zjistit, zda je možné města mezi společnosti rozdělit tak, aby žádná dvě propojená města nepatřila stejné společnosti?

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

Máme zadaná města a propojení mezi některými dvojicemi měst. Vaším úkolem je navrhnout algoritmus, který určí, zda je možné rozdělit všechna města mezi zbylé 2 společnosti tak, aby žádná dvě propojená města nepatřila stejné společnosti. Pokud takové rozdělení existuje, váš postup by měl jedno z platných rozdělení najít.

K řešení této úlohy se Ti může hodit prostudovat si sekci o grafech v naší základní kuchařce a taky naši grafovou kuchařku.

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í.

Putovní přednášky

Putovní přednášky jsou přednášky vysokoškoláků informatiků pro středoškoláky. Probíhají na středních školách v různých koutech republiky. Akce vždy trvá přibližně půl dne, proběhnou během ní čtyři informatické přednášky (jejich přesné zaměření závisí na místě konání) a diskuse o studiu na vysoké škole.

Naším cílem je přiblížit středoškolákům teoretickou informatiku – že něco takového vůbec existuje, o co v ní zhruba jde, kde se dá uplatnit, … Přednáškových akcí existuje víc, ale mnohé z nich jsou kvůli místu nebo času konání pro většinu studentů nedostupné. A tak když nemůžou studenti přijet za přednáškami, musí přednášky přijet za studenty. Přesně o to se Putovní přednášky snaží.

Pokud Vás putovní přednášky zaujaly tak můžete oslovit svoje učitele nebo napsat na prednasky@ksp.mff.cuni.cz, a my Vám zkusíme domluvit přednášky u Vás ve škole. Když chcete vědet více podívejte se na náš web:
https://ksp.mff.cuni.cz/akce/putovni-prednasky/.