Druhá série začátečnické kategorie třicátého třetího ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Dostává se vám do rukou zadání druhé série 33. 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í série. Ty nejúspěšnější z vás na jaře pozveme na týdenní soustředění (pokud to aktuální situace dovolí), na kterém se toho spoustu dozvíte a zároveň si užijete hromadu neopakovatelné zábavy.
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í!
- Termín série: neděle 6. prosince ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 13. prosince
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak sepsat řešení: viz ukázková úloha MO-P
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
Zadání úloh
33-Z2-1 Stánkař (8 bodů)
Kevina už nebavilo sedět doma, a tak se šel projít do parku. Posadil se a pozoroval stánek s občerstvením. Zaujalo ho, že někteří lidé přijdou ke stánku a počkají si, než jsou obslouženi, zatímco jiní po chvilce frontu opustí a odejdou. Aby důvod tohoto chování rozlousknul, začal si dělat poznámky. Po chvíli pozorování na to přišel – zákazníci nikdy nečekají déle než 10 minut.
Obsloužení zákazníka trvá prodavači 1 minutu a obsluhuje zákazníky tak, jak přišli do fronty. Zákazníci jsou bohužel netrpěliví a nechtějí čekat déle než 10 minut na svou objednávku. Pokud nejsou včas obslouženi, odejdou (tedy když zákazník přijde v čase T, tak ho již není možné obsloužit v čase T+10, protože v tu chvíli se otočil a odchází).
S touto myšlenkou se Kevin podíval do svých poznámek a zjistil, že vlastně neví, kolik zákazníků bylo obslouženo. Pomůžeš mu to spočítat?
Formát vstupu: Na prvním řádku vstupu je číslo N udávající celkový počet zákazníků. Na dalších N řádcích pak jsou časy příchodu jednotlivých zákazníků, zákazník je popsán časem příchodu v minutách od otevření stánku (celé kladné číslo). Zákazníci jsou seřazeni podle času příchodu.
Formát výstupu: Jedno číslo, počet obsloužených zákazníků.
14 0 0 0 0 1 1 1 1 2 2 2 2 2 7
13
Prodavač obslouží jen 13 zákazníků ze 14, protože předposlední čekání ve frontě vzdá.
33-Z2-2 Kulinářský hlavolam (10 bodů)
Móda televizních soutěží ve vaření zasáhla i Sáru a zrovna včera dávali velké finále. Sára o něm nadšeně vypráví Kevinovi: „Jeden finalista měl dokonce celou řadu sporáků nejrůznějších velikostí a ještě roztodivnější sadu hrnců.“ Kevin ale jen nevěřícně kroutí hlavou. Podle jeho názoru musel buďto stavět větší hrnce na menší plotýnky, nebo dokonce více hrnců na jednu – obojí velké kuchařské hříchy.
Pomozte Sáře dokázat, že si nevymýšlí a že pro dané plotýnky a hrnce lze najednou rozestavět všechny hrnce na plotýnky tak, aby platilo, že každý hrnec stojí na alespoň tak velké plotýnce, jako je on sám, a na každé plotýnce stojí nejvýše jeden hrnec.
Formát vstupu: Na prvním řádku vstupu jsou čísla N a K udávající počet plotýnek a počet hrnců. Následuje N řádků s velikostí každé plotýnky a poté K řádků s velikostí každého hrnce.
Formát výstupu: Pro každý hrnec vypište řádek s číslem hrnce a číslem plotýnky, na kterou ho postavíte, abyste splnili podmínky výše (číslujeme od jedničky). Slibujeme, že vždy bude existovat alespoň jedno řešení. Pokud je možností, jak hrnce rozestavit, více, vypište libovolnou z nich.
4 4 5 1 3 3 1 2 3 4
1 2 2 3 3 4 4 1
33-Z2-3 Rostoucí funkce (12 bodů)
Kevinova třída ve škole na hodinách matematiky zrovna začala probírat funkce. Kevina to však nebavilo, nedával pozor a dělal neplechu. Aby nerušil, dostal od učitele speciální úkol:
„Kevine, jak jistě víš, funkcemi můžeš přepočítávat nějaký vstup na nějaký výstup. Počítat toto je pro tebe příliš jednoduché, já bych po tobě ale chtěl, aby jsi mi zde tuto funkci vyhodnotil pozpátku. Dám ti výsledek a chtěl bych od tebe vědět, co musím do funkce vložit, abych ho dostal.“
S těmito slovy podal Kevinovi papír, kde bylo napsáno:
Kevin se na papír vyděšeně podíval a prohlásil: „Vždyť je to polynom 4. stupně! K tomu nedokážu spočítat inverzní funkci!“.
Učitel se pousmál. „To máš jistě pravdu! Slíbím ti, že inverzní funci počítat nemusíš. Budu ti totiž dávat jenom taková y, ke kterým existuje x mezi 1 a 100.“
Kevin se špetkou sarkasmu poděkoval a začal si črtat graf. Zkusil funkci vyčíslit pro pár hodnot:
f(1) = 1 628, f(2) = 4 021, f(3) = 6 956, f(99) = 58 479 404
„Hmm, to skoro vypadá, jako by funkce stále rostla!“ pomyslel si. Zkusil to formálně ověřit a zjistil, že tomu tak opravdu je. Funkce byla v intervalu mezi 1 a 100 rostoucí. „Toho bych mohl využít!“ pomyslel si Kevin. „Mohl bych zkusit odpověď tipovat a postupně vylepšovat! To bude ale dřina...“ Dokážete Kevinovi pomoct?
Na vstupu dostanete číslo y zapsané s přesností na dvě desetinná místa a vaším úkolem bude najít takové x z rozsahu 1 až 100 (včetně), které po dosazení do vzorce výše dá (po zaokrouhlení na dvě desetinná místa) to stejné y. Slibujeme, že takové x bude vždy existovat.
Formát vstupu: Na prvním řádku dostanete celé číslo N udávající počet dotazovaných čísel y. Na dalších N řádcích pak naleznete vždy jedno y zapsané jako desetinné číslo s tečkou s přesností na nejvýše dvě desetinná místa.
Formát výstupu: Na N řádků výstupu uveďte pro každé y ze vstupu nalezenou hodnotu x. Zapište ji jako desetinné číslo s desetinnou tečkou a libovolným počtem desetinných míst.
3 4176242.75 20858.06 34421.1
57.123 7.1452 18.00135
Upozornění: Doporučujeme používat 64-bitová floatová čísla, tedy pokud váš
programovací jazyk rozlišuje single a double precision floaty, tak použijte
double precision floaty (většinou datový typ double). Také si dejte pozor
na zaokrouhlování při výpisu. V Pythonu by při normálním použití nemělo být potřeba nic
z toho řešit. Kdyžtak nám napište na
zdrojaky@ksp.mff.cuni.cz.
33-Z2-4 Měření plachty (14 bodů)
V rámci příprav na nadcházející letní prázdniny se Kevin rozhodl, že si postaví loď. Začal tím, že si pořídí velkou plachtu, aby mu loď plula co nejrychleji.
Po příchodu do přístavu ale zjistil, že mu prodají pouze plachtu takových rozměrů, aby šla napnout mezi dva stěžně, podle kterých se plachty měří. Šířku plachty udává vzdálenost stěžňů a výška je rovná výšce menšího z nich.
Praktický kurz programování
Pokud Tě lákají praktické úlohy, ale ještě neumíš žádný programovací jazyk, tak se můžeš podívat na náš Základní kurz programování, kde se můžeš naučit základy Pythonu: https://ksp.mff.cuni.cz/kurzy/zkp/.
Seriál o počítačové grafice
V KSP-H právě běží seriál úloh o počítačové grafice a generování obrazu pomocí shaderů. Obtížnostně by ho měli zvládat i řešitelé KSP-Z, proto se neváhejte zapojit také. Všechny díly seriálu lze odevzdávat po celý ročník i zpětně, více detailů naleznete v aktuálním zadání KSP-H.
Zdrojáky praktických úloh
Ř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š:
- Jakou úlohu by měl program řešit.
- Slovní popis, co by měl program podle Tebe dělat.
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í.