První série začátečnické kategorie třicátého druhé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 první série 32. ročníku KSP-Z, neboli Korespondenčního Semináře z Programování, Začátečnické kategorie. Jedná se o korespondenční soutěž spočívající v řešení jednodušších programátorských úloh, které vychází během školního roku. Zapojit se může každý středoškolák i základoškolák, ty úspěšnější z vás pak na jaře pozveme na týdenní soustředění, na kterém se toho spoustu dozvíte a zároveň si užijete hromadu neopakovatelné zábavy. 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: 18. listopadu v 8:00, praktické úlohy za třetinu bodů až do 25. listopadu
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

Zadání úloh

• 32-Z1-1: Kevin v papírnictví
• 32-Z1-2: Chybná účtenka
• 32-Z1-3: Školní knihy
• 32-Z1-4: Plánek školy
• 32-Z1-5: Nábor basketbalistů
• 32-Z1-6: TOI TOI

32-Z1-1 Kevin v papírnictví (8 bodů)

Kevin se po prázdninách zase vrací do školy. Jako obvykle dostal seznam pomůcek, které si má obstarat. Malé sešity, velké sešity, pravítko, pastelky, barvy na výtvarku, učebnice na češtinu a dějepis a možná i novou aktovku. To vypadá na velký nákup!

Kevin se tedy vydal do obchodu. Jak dává věci do košíku, píše si i seznam cen. V tom si ale uvědomí, že má jen P korun. Kolik nejméně z N věcí v košíku musí Kevin vyhodit, aby mu P korun stačilo?

Tvar vstupu: Na prvním řádku se nachází počet věcí v košíku N a počet korun P, které Kevin může utratit. Na druhém řádku je pak seznam cen věcí v košíku, tedy N kladných čísel oddělených mezerami.

Tvar výstupu: Vypište jedním číslem nejmenší počet věcí, které musí Kevin z košíku vyhodit.

5 59
8 20 30 1999 40

2

Řešení

32-Z1-2 Chybná účtenka (10 bodů)

Kevin oželel aktovku, na kterou mu nezbyly peníze, a nakoupil jen sešity a nějaké další drobnosti. Peníze mu tak tak vyšly, ještě že to měl dobře spočítané. A co že si to teda všechno koupil? Kevin se podíval na účtenku…

Moment, kde je napsaný ten sešit, který drží Kevin v ruce? A co je tahle změť písmenek na třetím řádku? To si přeci Kevin nekupoval! Kevin chvíli koukal na účtenku a přemýšlel, co se mohlo stát. Pak na to ale přišel: tiskárna musela omylem vytisknout nějaké znaky navíc. Když je vyškrtá, dostane správný název položky, kterou si koupil. Kevin tedy vzal první sešit a začal hledat, která položka z účtenky by to mohla být.

Tvar vstupu: Na prvním řádku bude název věci, kterou si Kevin koupil. Na druhém řádku dostanete číslo N, což je počet položek z účtenky, které budou následovat, každá na samostatném řádku.

Tvar výstupu: Vypište pro každou položku z účtenky na samostatný řádek ANO nebo NE podle toho, zda je možné z názvu položky vyškrtat některá písmenka, abychom dostali název zakoupené věci.

sesit
3
sesivactka
kalkjulascka
swessit

ANO
NE
ANO

Řešení

32-Z1-3 Školní knihy (10 bodů)

Kevin si ještě před začátkem školy vyskládal na stůl do komínku všechny učebnice, které má. Protože je tak trochu lajdák, každou knihu položil, jak mu zrovna přišla pod ruku, a tak byla každá kniha otočená jiným směrem.

Za Kevinem do pokoje přišla jeho mladší sestra Zuzka. Ta je naopak velmi pořádná, a tak chtěla Kevinovi všechny knihy srovnat, aby byly všechny otočené stejným směrem. Může libovolnou knihu otočit o nějaký celočíselný počet stupňů a zároveň tím otočí i všechny knihy nad ní. Jak to má Zuzka udělat, aby knihy musela otáčet co možná nejméně?

Tvar vstupu: Na prvním řádku je počet knih N. Na dalších N řádcích pak je celočíselný směr otočení knihy ve stupních.

Tvar výstupu: Vypište jediné číslo: o kolik stupňů musíme nejméně všechny knihy dohromady otočit, aby byly na konci všechny otočené ve stejném směru.

4
30
60
350
50

160

Řešení

32-Z1-4 Plánek školy (12 bodů)

Kevin na webových stránkách školy našel plánek všech místností. Je takový jednoduchý, jsou tu jen křížky jako zdi a tečky jako volný prostor. To ale Kevinovi stačí, aby mohl školu prozkoumat, ještě než tam půjde.

Tohle je Kevinova třída, tady je zase laboratoř biologie a támhleta velká místnost musí být tělocvična, kde se vždy při zahájení školního roku celá škola sejde. Bývá tam při takovém počtu lidí ale trochu těsno, a tak Kevina napadlo, jestli se ve škole nenachází ještě nějaká větší místnost. Jak velká je největší místnost ve škole? Místnosti jsou oddělené zdmi a každá místnost se skládá ze všech volných políček, která spolu sousedí stěnou.

Tvar vstupu: Na prvním řádku jsou dvě čísla M a N, šířka a výška plánku. Na každém z dalších N řádků se nachází M znaků, buď . (volné pole), nebo X (zeď).

Tvar výstupu: Vypište jedno číslo: počet políček, z kterých se skládá největší místnost. Políčka spolu sousedí jen stranou, rohem ne.

6 5
XXXXXX
X.X..X
XXX..X
X..X.X
XXXXXX

5

Řešení

32-Z1-5 Nábor basketbalistů (12 bodů)

Když Kevin přišel konečně do školy, hned ho oslovil nějaký vysoký mladík, že dělá nábor do školního basketbalového týmu a jestli se nechce přidat. To se ví, že by si Kevin rád basketbal vyzkoušel, ale musí se nejdřív zúčastnit výběrového řízení. Školní basketbalový klub je totiž velmi prestižní, a tak chce přijmout jen dvanáct nejvyšších kluků, protože ti budou určitě nejlepšími hráči basketbalu.

Kevin není až tak vysoký, a tak ho napadlo, že vymyslí systém, jak přijímání nových hráčů zjednodušit a třeba ho za to do basketbalového klubu přijmou jen tak.

Dostanete posloupnost výšek všech zájemců o basketbal. Vaším úkolem je najít dvanáct nejvyšších hráčů, které má basketbalový klub přijmout.

Řešení

32-Z1-6 TOI TOI (14 bodů)

Kevin se nakonec do basketbalového klubu dostal i se svým kamarádem Petrem. Dnes hrají svůj první zápas. Kevin dal napoprvé čtyři koše a Petr tři, to není pro začátek vůbec špatné! Teď mají zrovna pauzu, a tak si šel Kevin odskočit.

Hraje se v moderní venkovní hale. Je tu nové hřiště, mají tu čipy na otvírání všech dveří a dokonce i na toaletách mají inovativní systém na přiřazování kabinek. Stojí tu v řadě N toalet. Když člověk přijde, dostane od systému přidělenou nějakou volnou toaletu nebo odpověď, že je všude plno. Když se kabinka uvolní, systém to samozřejmě také zaznamená, aby ji mohl zpřístupnit dalšímu příchozímu.

Popište datovou strukturu, která umožní systém efektivně naimplementovat. Musí umět rychle obsloužit nově příchozího a dát mu nějakou volnou kabinku. Zároveň musí umět zaznamenat odchod člověka z nějaké konkrétní toalety.

A co si pod takovým popisem datové struktury představujeme? Chtěli bychom vědět, co si budete ukládat, jaký to bude mít formát a jak budou probíhat jednotlivé operace nad vaší datovou strukturou. Ideálně s jejich složitostí. Samozřejmě bychom chtěli, abyste využili co nejméně paměti a aby vše bylo co nejrychlejší.

Řešení