Třetí 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.
Dostala se k vám právě třetí série 33. ročníku KSP-Z, neboli Korespondenčního Semináře z Programování, Začátečnické kategorie.
Dvě série z letošních pěti jsou sice již za námi, ale i tak se může stále zapojit každý středoškolák i základoškolák. Také doufáme, že nám aktuální epidemická situace dovolí uspořádat týdenní jarní soustředění s přednáškami a zážitkovými aktivitami. Svoje šance na přijetí na toto soustředění můžete velmi zvýšit účastí v alespoň jedné sérii KSP-Z.
Pokud budete mít jakoukoliv otázku, neváhejte se zeptat. Kontaktní adresy najdete v patičce letáku. Přejeme hodně štěstí!
- Termín série: neděle 14. února ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 21. února
- 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-Z3-1 Šikmá věž z krabic (8 bodů)
Kevin našel na půdě staré krabice a kyblík lepidla a rozhodl se, že si z nich postaví šikmou věž. Chtěl by, aby byla šikmá věž co možná nejšikmější, tedy aby ve vodorovném směru dosáhla co možná nejdále.
Nejprve si vybere jednu krabici a tu lepidlem přilepí na zem. Každou další krabici jde na předchozí umístit jen, pokud její těžiště leží nad předchozí – nechceme, aby nám krabice přepadla, než lepidlo zaschne. Po zaschnutí lepidla už krabice drží pevně a jde na ni lepit další. Krabice je možné položit buď na výšku, nebo na šířku.
Formát vstupu: Na prvním řádku vstupu dostanete číslo N udávající počet krabic. Na dalších N řádcích následují celočíselné rozměry krabice (výška, šířka) oddělené mezerou.
Formát výstupu: Výstupem je největší šířka šikmé věže, kterou jde z krabic postavit, na jedno desetinné místo. Šířku věže měříme včetně první krabice, viz ilustrační obrázek.
5 5 4 1 3 3 4 1 1 4 3
11.0
33-Z3-2 Přečasování titulků (10 bodů)
Kevin, Sára a Petr se po dlouhé karanténě sešli na sledování filmů. Z online videopůjčovny si půjčili zajímavý film o hroších samurajích v Japonsku, v japonštině s českými titulky. Jaké ale bylo jejich zklamání, když zjistili, že titulky na film nesedí a jsou asi posunuté a ještě k tomu jinak rychlé.
Kevin se to rozhodl rychle vyřešit. Našel v titulcích na začátku filmu jedno zvolání hrošího samuraje, které zvládl identifikovat i v japonském originále, a stejně tak se mu povedlo najít podobné zvolání někde ve druhé polovině filmu.
Má teď tedy správné časy začátků dvou titulků a potřeboval by upravit celé titulky tak, aby po přečasování (tedy po změně rychlosti a po posunutí) začínaly ony dva titulky ve správných časech (v těch, které Kevin nalezl).
Formát vstupu: Na prvním řádku naleznete číslo N udávající počet titulků. Na dalších dvou řádcích pak naleznete dva Kevinem nalezené titulky se správnými časy, ve kterých mají začínat – každý z nich je zadaný textem titulku a časem správného začátku oddělenými mezerou.
Pak následuje N řádků s titulky, kde na každém řádku jsou mezerou oddělené čas začátku, čas konce a text titulku. Všechny texty titulků jsou vždy jedno slovo bez mezer složené z malých a velkých písmen anglické abecedy, každé slovo je navíc unikátní (žádné dva titulky nemají stejný text). Časy začátků a konců titulků jsou kladná celá čísla (udávají počet snímků od začátku filmu) a titulky jsou na vstupu v chronologickém pořadí.
Formát výstupu: Na N řádků výstupu opište vstupní titulky, ale se správně přečasovanými časy – tedy každý řádek bude obsahovat mezerou oddělený čas začátku, čas konce a text titulku. Časy zaokrouhlete na celá čísla snímků. Naše Odevzdávátko uzná i časy posunuté o jeden snímek libovolným směrem, abyste nemuseli příliš řešit zaokrouhlovací chyby.
4 jsem 54 vystraseny 82 222 246 jsem 249 282 malyZtraceny 306 327 vystraseny 351 387 hroch
54 62 jsem 63 74 malyZtraceny 82 89 vystraseny 97 109 hroch
Příklad: Pro titulky výše bylo potřeba časy snímků vydělit trojkou a pak posunout o 20 snímků blíž k začátku filmu, aby seděly na Kevinem nalezené správné pozice.
33-Z3-3 Chamtivý stánkař (12 bodů)
Kevin se šel opět projít do parku a usadil se na lavičku, ze které v minulé sérii pozoroval stánkaře a frontu před jeho stánkem (viz první úlohu minulé série).
Od minula se ale dění u stánku velmi změnilo, protože stánkař začal nabízet dva druhy nápojů, čaj a limonádu. Kevin pozoroval, že někteří lidé přijdou ke stánku a jsou téměř hned obslouženi a jiní před stánkem dlouho čekají. Aby důvod tohoto chování rozlousknul, začal si dělat poznámky. Po chvíli pozorování na to přišel – objevil klíč, podle kterého prodavač některé zákazníky upřednostňuje:
Jak již bylo řečeno, tak prodavač prodává celkem dva nápoje, čaj a limonádu. Vyřízení jednoho zákazníka mu trvá 1 minutu a přednostně obsluhuje zákazníka, který čeká nejdéle. Ovšem na čaji má větší marži, takže pokud někdo chce čaj, ignoruje všechny požadující limonádu. 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 budou údaje o jednotlivých zákaznících. Každý zákazník je popsán časem příchodu v minutách od otevření stánku (celé kladné číslo) a velkým písmenem C (čaj) nebo L (limonáda). Zákazníci jsou seřazeni podle času příchodu.
Formát výstupu: Výstupem je jediné číslo představující počet obsloužených zákazníků.
14 0 L 0 L 0 C 0 L 1 C 1 C 1 C 1 C 2 C 3 C 5 C 8 C 10 C 10 L
12
Obslouží jen 12 zákazníků ze 14, protože druhý a čtvrtý zákazník čekání vzdají.
33-Z3-4 Statek (14 bodů)
Kevinovi v parku začínala být zima. Už aby bylo zase léto, pomyslel si. Těšil se za dědečkem na statek. Nejenže je na statku spoustu zvířat, se kterými si se Zuzkou mohou hrát, ale Kevin si zamiloval jízdu na kombajnu. Samozřejmě řídí dědeček, ale Kevin se už těší, až si to bude moct také zkusit. Sedět celý den za volantem kombajnu, jezdit po polích a sklízet, to by ho bavilo. A třeba si pořídit i vlastní statek. Kevin vytáhne mobil, zapne mapy a začne přemýšlet, kde by si mohl takový statek postavit. Chce najít nějaké místo s velkými poli hned vedle, aby mohl neustále jezdit s kombajnem a sklízet. Pomůžete Kevinovi vybrat ideální místo k postavení statku?
Mapa je čtvercová síť, jejíž políčka jsou buď pole, nebo lesy. Statek zabírá právě jedno políčko z mapy a lze ho postavit na kterémkoli z nich, toto políčko se pak stává políčkem statku. Kombajn se nachází na statku a odtamtud také vyjíždí, jezdit pak dokáže jen po políčkách s poli a se statkem, lesem projet nedokáže. Mezi políčky se umí přesunovat buď vodorovně nebo svisle, šikmo jezdit neumí.
Vymyslete algoritmus, který dostane na vstupu mapu lesů a polí a pomůže Kevinovi najít takové místo pro nový statek, ze kterého kombajn dokáže dojet na co nejvíce políček polí. V jakém pořadí bude jednotlivá políčka nakonec kombajn sklízet nás už nezajímá.
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í.