Třetí série začátečnické kategorie dvacátého devátého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

• Termín série: 6. března 2017 v 8:00
• 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

• 29-Z3-1: Želva na dvorku
• 29-Z3-2: Písemka z angličtiny
• 29-Z3-3: Šestková čísla
• 29-Z3-4: Zdobení stromečku
• 29-Z3-5: Prvočíselné rozklady
• 29-Z3-6: Trable s dominem

29-Z3-1 Želva na dvorku (8 bodů)

„Stůj! Vždyť nám zbouráš sněhuláka!“ křičí Kevin. Výcvik Želvy šel totiž dobře, skutečně se naučila některé základní povely. Proto zkusili vzít Želvu ven, aby viděli, jak se popasuje s terénem. Jenže se Sárou se občas na povelech neshodnou a Želva slepě naráží do překážek.

Na čtverečkovaném zasněženém trávníku leží P překážek, u každé znáte její souřadnice a víte, že zabírá právě jedno políčko. Tam kde je překážka, nemůže Želva vkročit. Dokážete z povelů určit, kde Želva skončí?

Tvar vstupu: Na prvním řádku dostanete čísla P a N, kde P je počet překážek a N je počet povelů. Následuje P řádků se souřadnicemi překážek, pokaždé nejprve vzdálenost v západně-východním směru, potom v severo-jižním.

Vstup končí řádkem s N znaky povelů. Želva rozumí třem povelům: < znamená otoč se proti směru hodinových ručiček, > otoč se po směru hodinových ručiček a A popojdi o jedno políčko dopředu.

Želva začíná jako obvykle na políčku [0, 0], otočená na sever. Pokud povel nelze provést, Želva jej přeskočí. Překážka se nikdy nebude nacházet na počátečních souřadnicích Želvy.

Tvar výstupu: Vypište dva řádky. Na jednom budou souřadnice Želvy po tom, co vykoná nebo přeskočí všechny povely. Na druhém číslo, kolikrát želva v průběhu narazila do překážky.

1 5
0 1
AAA>A

1 0
3

Želva se v příkladu třikrát pokusí narazit do překážky, teprve pak se otočí a popojde.

Řešení

29-Z3-2 Písemka z angličtiny (10 bodů)

Želva ovšem není zvíře zvyklé na zimu, proto museli rychle domů. Také Kevin se už musí učit, hned po prázdninách píšou písemku z angličtiny. Aby prospěl, musí se naučit velkou spoustu slovíček.

Ze zoufalství Kevina napadlo, že si vyrobí tahák. Ne že by ho chtěl při písemce použít, to se přeci nesmí, ale výrobou taháku se člověk nejvíce naučí.

Slovíčka, která se Kevin učí, mají zajímavou vlastnost: velmi často se stává, že přilepením přípony za jedno slovíčko vznikne druhé. Dalo by se také říci, že první slovíčko je prefixem druhého.

Například slovo „hra“, je prefixem slova „hračka“. Nebo třeba slova „a“, „advent“ a „adventure“ jsou prefixy slova „adventurer“.

Aby Kevin uspořil co nejvíce místa, napadlo ho, že napíše na tahák takové slovíčko, které má v sobě nejvíce jiných slovíček jako prefix. Jednotlivé prefixy pak označí a přeloží zvlášť, ale nejprve by potřeboval takové slovíčko najít.

Tvar vstupu: Vstupem je slovník. Na prvním řádku je číslo N, označující počet slov ve slovníku. Následuje N řádků se slovy složenými z malých písmen anglické abecedy.

Tvar výstupu: Na výstup vypište jediné slovo, které má nejvíce jiných slov ze slovníku jako prefix.

Řešení

29-Z3-3 Šestková čísla (10 bodů)

Z pilného učení vytrhl Kevina až Petr, který přiběhl s revoluční myšlenkou. Vymyslel totiž nový způsob kódování čísel – šestková čísla.

Každému, kdo zná římská čísla, bude jejich popis povědomý. Šestková čísla používají místo arabských číslic písmena latinky. Každé písmeno má svou hodnotu podle tabulky.

Písmena, tedy vlastně šestkové číslice, se píší od největší k nejmenší. Potom je hodnota šestkového čísla rovna součtu hodnot jednotlivých číslic. Příklady:

Pokud jsou číslice uvedené v jiném pořadí, znamená to, že se hodnoty odečítají. Je však možné odečítat pouze číslici o jedna menšího řádu, a to nejvýše dvakrát. Odčítané číslice navíc musí být zapsané právě před poslední číslicí většího řádu. Například:

Netrvalo dlouho, než si naši kamarádi uvědomili, že tento zápis není jednoznačný. Například číslo čtyři se dá zapsat buď s odčítáním jako JJS, nebo bez něj jako JJJJ. Rozhodli se, že jako hlavní označí zápis, který nemá nikdy čtyři stejné číslice za sebou. Pouze číslice Z smí být zapsána, kolikrát je potřeba.

Navíc, číslo v hlavním zápisu nesmí mít nikdy zbytečné číslice navíc. V čísle JSJ se jednička odečítá, aby se vzápětí zase přičetla. Hlavní zápis čísla šest je samozřejmě S.

Aby se jim s čísly lépe pracovalo, rádi by si pořídili takový program, který dokáže načíst číslo v libovolném platném zápisu a převést ho do zápisu hlavního. A protože to chtějí rozjet ve velkém, potřebují, aby to program dokázal s více čísly v jednom souboru.

Tvar vstupu: Na prvním řádku je číslo T (v obyčejném desítkovém zápisu), které označuje, kolik vstupů se v souboru nachází. Následuje T řádků, na každém je jedno číslo v šestkovém zápisu. Každé číslo je platné podle výše uvedených pravidel, ale nemusí být v hlavním zápisu.

Tvar výstupu: Vypište čísla ze vstupu v hlavním šestkovém zápisu, každé na zvláštní řádek.

3
JJJJ
SSSSSS
JJSJJ

JJS
T
S

Řešení

29-Z3-4 Zdobení stromečku (12 bodů)

Zatímco si kluci hrají s čísly, Sára a Zuzka vzpomínají, jak zdobily vánoční stromeček. To byla krása, takových ozdob! Už dlouho se jim to takhle nepovedlo.

Každá ozdoba má tvar barevného blýskavého řetězu, který se zavěsí mezi dvě větve. Ozdobné řetězy se můžou libovolně křížit, z jedné větve jich může vést libovolně mnoho. Řetězy se ovšem nedají věšet jinam než mezi dvě špičky větví. Navíc, řetěz se nesmí pověsit mezi dvě větve, mezi kterými už řetěz visí.

Na původně holý stromeček holky postupně zavěšovaly řetězy, dokud si toho Sára nevšimla. „Tohle přeci není strom, vždyť obsahuje kružnice!“ A měla pravdu. V terminologii grafů bychom mohli říct, že větve jsou vrcholy a řetězy mezi nimi tvoří hrany. Po chvíli zdobení se na našem stromečku objevil cyklus.

Bez použití grafových pojmů to znamená, že začneme-li na větvi S, můžeme po řetězích přeskákat několik jiných větví a skončit opět na větvi S, aniž bychom použili nějaký řetěz dvakrát.

Teď se ale kamarádky nemůžou dohodnout, která z nich vlastně přidala onen řetěz, který vytvořil první kružnici. Pomůžete jim?

Tvar vstupu: Na prvním řádku jsou čísla N a M. N je počet větví, které jsou očíslovány 1 …N. M je počet řetězů. Na dalších M řádcích jsou vždy dvě čísla větví, mezi kterými je pověšen řetěz. První řetěz má číslo 1. Řetězy jsou v souboru v takovém pořadí, v jakém byly věšeny na stromeček.

Tvar výstupu: Na výstup vypište číslo řetězu, který vytvořil první kružnici, tedy udělal z lesa obecný graf.

4 5
1 2
2 3
3 4
3 1

4

Řešení

29-Z3-5 Prvočíselné rozklady (12 bodů)

Vrátíme se k číslům. Určitě už jste slyšeli, co to je prvočíslo. Pro jistotu: prvočíslo je takové číslo, které je beze zbytku dělitelné pouze jedničkou a sebou samým.

Každé číslo je možné zapsat jako součin jiných prvočísel, potom mluvíme o prvočíselném rozkladu. Ten je až na zbytečné jedničky a pořadí činitelů jednoznačný.

Jak rychle dokážete spočítat prvočíselný rozklad? A jak rychle to dokážete, pokud víte, že dotazů bude více?

Podobně jako v minulé sérii, dostanete číslo M a nějaký čas na přípravu. Potom bude přicházet N dotazů na rozklad čísla 1 < x ≤ M, které byste měli zodpovědět co nejrychleji.

Nezapomeňte ve svém řešení vyjádřit, kolik času a paměti potřebujete na předvýpočet vzhledem k M, a kolik času na jeden dotaz.

Řešení

29-Z3-6 Trable s dominem (14 bodů)

Nevíme jak vy, ale naši seriáloví přátelé o Vánocích také pekli cukroví. Na ty loňské si pořídili speciální formičky, které mají tvar dominové kostky. Každý výsledný kousek cukroví má dvě poloviny a každá z nich má na sobě nějaký vánoční symbol.

Formičky se špatně myjí, proto se kamarádi rozhodli, že použijí jen některé, zato bude od každého zašpiněného druhu dostatečný počet kousků cukroví. Máme tedy jen některé
kombinace symbolů, od každé kombinace ale neomezené množství dominových kostiček.

Když dopekli, lákalo je si s cukrovím taky trochu pohrát a postavit dlouhého hada. Rozdělili se na dvě skupiny a každá začala stavět hada z jedné strany. Samozřejmě s tím, že dvě kostičky za sebou musí navazovat společným symbolem.

Když ale dostavěli až k sobě tak zjistili, že nemají způsob, jak dvě části hada spojit. Ať hledali jak hledali, potřebné kostičky jim chyběly. Dokonce jim ani nepomohlo, když části hada posouvali a tím měnili počet kostiček, které se mezi ně vejdou.

Příště už by se tomu již chtěli vyvarovat. Dokážete vymyslet algoritmus, který pro zadaný seznam formiček rozhodne, jestli jde každé dva hady spojit?

Řešení