První série začátečnické kategorie dvacátého sedmého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
- Termín série: 18. listopadu 2014 8:00
- 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
- 27-Z1-1: Na zastávce
- 27-Z1-2: Kalkulačka
- 27-Z1-3: Slovník T9
- 27-Z1-4: Lyžař
- 27-Z1-5: Cédéčko z koncertu
- 27-Z1-6: Žárovky
27-Z1-1 Na zastávce (8 bodů)
Kevin jel se třídou na výlet do zoo, ale nejeli tam sami. Na autobusové zastávce stálo plno skupinek výletníků, turistů, rodin s kočárky, školních tříd, studentů a dalších cestujících, kteří tím směrem chtěli jet taky. Byla to pěkná tlačenice. Žádná skupinka se nechtěla rozdělit, aby autobusem odjela jenom její část, ani nechtěla pustit žádnou jinou skupinku před sebe. Všechny skupinky stály ve frontě v pořadí, v jakém na zastávku přišly.
Naštěstí každých deset minut přijížděl prázdný autobus. Vešlo se do něj M lidí. Když se některá skupinka už nevešla celá, nechala autobus odjet ne zcela zaplněný a čekala na další. A čekala a čekala.
Takové čekání je samozřejmě strašná nuda. Kevina by tedy zajímalo, jak dlouho ještě bude čekat. Povíte mu to?
Tvar vstupu: Na prvním řádku budou čísla M a N oddělená mezerou. M udává, kolik lidí se vejde do jednoho autobusu, bude to mezi 20 a 250. N je počet skupinek, které na zastávce čekají, těch bude mezi 1 a 105. Následovat bude N čísel udávajících velikosti skupinek, každé na samostatném řádku. Velikosti budou v rozmezí 1 až M včetně. Kevin je v poslední skupince.
Tvar výstupu: Na výstup vypište jedno celé číslo udávající, kolikátým autobusem odjede poslední skupinka ze zastávky.
80 5 2 40 40 2 42
3
V každém ze tří autobusů pojede 42 lidí.
27-Z1-2 Kalkulačka (10 bodů)
Ajéje! Stala se strašná věc. Kevin si jednou před písemkou půjčil od kamaráda Petra kalkulačku. Petr ji chce vrátit, ale Kevin ji nemůže najít. Buďto ji má někde doma, nebo ji ztratil, nebo mu ji snědl hroch, nebo…
Každopádně Petr ji musí dostat zpět. A Kevin ji nemá. Ta kalkulačka ale byla
dost jednoduchá. Uměla počítat jen s celými čísly – sčítat je (+),
odčítat (-), násobit (*) a celočíselně dělit (/). Neovládala
závorky ani přednost násobení před sčítáním, všechny operace vyhodnocovala
v pořadí, v jakém byly zadány. Navíc pokaždé, když jste zmáčkli tlačítko
s operátorem, vypsala vám dosavadní mezivýsledek.
Když se někdo pokoušel dělit nulou, nezmizela ani neshořela,
jen nenápadně místo toho provedla operaci přičtení nuly,
doufajíc, že si toho uživatel nevšimne.
Kevin se tedy rozhodl, že Petrovi kalkulačku vyrobí, aby mu ji mohl vrátit. Pomůžete mu s tím?
Tvar vstupu:
Na jednom jediném řádku vstupu budete mít korektní výraz k vyhodnocení.
Ten je tvořen nezápornými celými čísly oddělenými operátory +,
-, *, /. Mezi každou dvojicí sousedních čísel je
právě jeden operátor. Navíc jsou čísla oddělena od operátorů mezerami.
Vstupní čísla budou z intervalu ⟨0, 109⟩,
všechny mezivýsledky se vejdou do ⟨-109, 109⟩.
Vstup má délku nejvýše 500 znaků, je ukončen =.
Tvar výstupu:
Na i-tý řádek vypište to, co bude na displeji kalkulačky po zmáčnutí
i-tého operátoru (jinými slovy hodnotu části výrazu od začátku po i-tý
operátor). Na posledním řádku nechť je finální výsledek, který se objeví
po stisku = (hodnota celého výrazu).
Všechny operace ve výrazu vyhodnocujte zleva doprava bez ohledu
na priority operátorů. Při dělení zaokrouhlujte záporná čísla
směrem k nule (tedy -5 / 3 = -1). Kdykoli se ve výrazu objeví sekvence „/ 0“,
interpretujte ji jako „+ 0“.
2 * 0 + 333 / 50 / 0 - 5 =
2 0 333 6 6 1
27-Z1-3 Slovník T9 (10 bodů)
„Píp píp!“ Ne, nejsme v zoo v pavilonu ptáků, jsme u hrochů. Kevinovi právě přišla esemeska od spolužačky Sáry. Někde se v tom stádu ztratila.
„Leti led si? Para“. Co to je? Takové zmatené zprávy občas posílá
Kevinova babička. A Sára.
Sára totiž používá slovník T9. Když píše esemesky, nemusí jednu klávesu zmáčknout třeba čtyřikrát, když chce napsat S. Stačí za každé písmeno stisknout příslušnou klávesu jen jednou, slovník z kombinace stisknutých kláves pozná, co chtěla napsat, a to slovo napíše.
Pro připomenutí, klávesnice většiny starších mobilních telefonů vypadala nějak takto:
Ne vždy ale T9 pozná přesně to, co Sára myslela. Více slov totiž může mít
stejnou kombinaci kláves. Občas se stane,
že slovník napoví špatně. Třeba když namačkáte tlačítka pro „Kevi kde
si? Sara“, může se objevit i to, co teď Sára poslala Kevinovi.
Kevina by zajímalo, která slova jsou v tomto ohledu nejnebezpečnější, tedy je může T9 zaměnit s co nejvíce jinými slovy. A to už je úkol pro vás.
Tvar vstupu: Na prvním řádku dostanete číslo 1≤ N ≤ 105 udávající velikost slovníku. Na dalších N řádcích bude vždy jedno slovo složené z písmen anglické abecedy, každé slovo bude dlouhé 1 až 15 znaků.
Tvar výstupu: Vypište největší skupinu slov, která mají všechna v T9 stejný zápis. Každé ať je na samostatném řádku. Pokud takových skupin existuje více, můžete si vybrat libovolnou.
6 punc jana lama runa suma puma
puma runa suma punc
27-Z1-4 Lyžař (12 bodů)
Je léto, sluníčko svítí, ptáčci zpívají, po sněhu ani památky…Tak proč si nezalyžovat? Máme přece travní lyže!
Kevin je právě na horách a lyžuje. Stojí na vrcholu sjezdovky před svou poslední jízdou, za chvíli půjde na chatu opékat párky. Sjezdovku už dobře zná, každé místo projel snad stokrát a pamatuje si, jak se mu které líbí. Všechna jsou podle toho ohodnocená celými čísly.
1
2 3
4 1 1
2 5 0 2
Kevin by tedy chtěl, aby součet ohodnocení míst, přes která při poslední jízdě projede, byl co největší.
Na travních lyžích se dá jezdit z kopce a přitom zatáčet doleva nebo doprava. Z každé pozice na svahu se tak dá dostat na nejvýše dvě další pozice ležící pod ní.
Tvar vstupu: Pro jednoduchost bude kopec zadán po řádcích. Na prvním řádku bude číslo N udávající výšku kopce. Na dalších N řádcích bude vždy na i-tém řádku i celých čísel udávajících ohodnocení míst na kopci na i-té hladině od vrcholu, čísla budou oddělena mezerami.
Jízda doleva je v našem zápisu svahu ekvivalentní sestupu na další řádek a jízda doprava sestupu na další řádek a posunutí o pozici doprava.
Tvar výstupu: Na výstup vypište jedno celé číslo udávající maximální součet ohodnocení poslední Kevinovy jízdy z prvního řádku na libovolné místo na spodním řádku.
4 1 2 3 4 1 1 2 5 0 2
12
Optimální cesta je pořád doleva (v našem zápisu rovně dolů), jen mezi předposledním a posledním řádkem zatočíme doprava. Její ohodnocení je skutečně 1 + 2 +4 +5 = 12.
27-Z1-5 Cédéčko z koncertu (12 bodů)
Kevin hraje na bicí ve studentské rockové kapele Velká tlama. V létě měli velký koncert, který nahrávali. Teď by chtěli začít fanouškům prodávat cédéčko se záznamem tohoto koncertu. Bohužel, vydat můžou jenom jedno a celý koncert se na něj nevejde, takže tam dají jenom jeden souvislý úsek. (Vystříhat jen něco nemohou, to by nedávalo posluchačům smysl.)
Koncert je pro naše účely posloupnost písniček, každá je určená svojí délkou. Jinak jsou nerozlišitelné.
Kapela by chtěla vybrat jednu souvislou část koncertu, a to tak, aby součet délek písniček přesně naplnil kapacitu CD. Fanoušci jsou totiž nároční a jedině takto budou spokojeni.
Které písničky má kapela vybrat?
Jinými slovy, na vstupu dostanete posloupnost celých čísel a číslo K. Navrhněte co nejefektivnější algoritmus, který nalezne v posloupnosti souvislý úsek se součtem právě K, nebo ohlásí, že v ní žádný takový není. Snažte se co nejlépe zdůvodnit, proč je váš algoritmus správný a efektivní.
27-Z1-6 Žárovky (14 bodů)
Na chatě Kevin s tatínkem spravuje elektriku, tedy vlastně ji spíš dělají celou znova. Teď zrovna světla v kuchyni.
V kuchyni mají N žárovek. Chtěli by k nim připojit vypínače tak, aby jejich nastavením mohli rozsvítit libovolný počet žárovek z rozsahu 0 až N. Jeden vypínač může rozsvěcet více žárovek.
Navrhněte pro ně řešení, které bude potřebovat co nejméně vypínačů pro zadané N. Pro plný počet bodů také dokažte, že menší počet jim stačit nebude.
Například pro N=5 potřebujeme tři vypínače: první rozsvěcí žárovku 1, druhý žárovky 2 a 3 a třetí ovládá 4 a 5. Snadno si rozmyslíte, že dva nestačí.