První série začátečnické kategorie dvacátého šestého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 6. ledna 2014 8:00. Řešení odevzdávejte elektronicky.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Zadání úloh

První čtyři úlohy (označené piktogramem počítače) jsou praktické. To znamená, že ke každé z nich máme na webu ke stáhnutí několik sad vstupů a body získáš za odevzdání správných výstupů k odpovídajícím sadám. Jak výstupy vygeneruješ (třeba v jakém jazyce napíšeš program, který je zpracuje), je už čistě na Tobě.


26-Z1-1 Kevin a magnety (8 bodů)


Praktická CodExová úlohaKevin má v krabičce N magnetů – obyčejných magnetických tyček, které mají na jednom konci pól + a na druhém -. Jednoho dne se rozhodl, že si v nich udělá pořádek.

Jeden po druhém magnety vyndaval z krabičky a pokládal je do řady na stůl. Někdy se spojily k sobě (pokud se setkaly opačnými póly), jindy se mezi nimi zase vytvořila mezera.

Kevina by zajímalo, do kolika částí se mu magnety spojily.

Tvar vstupu: Program na vstupu dostane na prvním řádku číslo N (1 ≤ N ≤ 1 000 000). Každý z dalších N řádků bude obsahovat buď řetězec +-, nebo -+ udávající, kterým směrem Kevin magnet položil.

Tvar výstupu: Na výstup vypište jediný řádek obsahující jedno celé číslo: počet oddělených částí, do kterých se magnety spojí.

Ukázkový vstup:
4
+-
+-
-+
+-
Ukázkový výstup:
3

Řešení


26-Z1-2 Piškvorky (10 bodů)


Praktická CodExová úlohaKevin sedí na hodině dějepisu. Bitvy, letopočty, děsná nuda. Raději si hraje se svým novým smartphonem a píše si s kamarádkou Sárou, která se ve vedlejší třídě nudí na hodině matiky. Aby si zkrátili dlouhou chvíli, rozhodli se hrát piškvorky.

Jejich aplikace na piškvorky ale není dokonalá a neumí poznat, jestli už někdo vyhrál. To si Kevin se Sárou uvědomili až po nějaké době, a tak by je nyní zajímalo, kolikrát kdo z nich vyhrál. Kevin má křížky a Sára kolečka.

Tvar vstupu: Na vstupu dostanete čísla SR udávající šířku a výšku hrací plochy (1 ≤ R,S ≤ 1 000). Na dalších R řádcích bude vždy S znaků X, O nebo ., kde X znamená křížek, O kolečko a . znamená prázdné políčko hrací plochy.

Tvar výstupu: Na výstup vypište jediný řádek se dvěma celými čísly oddělenými mezerou: počtem pětic křížků a počtem pětic koleček. Pětice mohou ležet v libovolném řádku, sloupci, nebo úhlopříčce.

Ukázkový vstup:
6 6
XXXXXO
.X..OX
..XO.X
..OX.X
.O..XX
OOOOOX
Ukázkový výstup:
4 3

Řešení


26-Z1-3 Zamilovaný dopis (10 bodů)


Praktická CodExová úlohaKevin působí jako bubeník ve studentské rockové kapele Velká tlama. Kapela během svého prvního veřejného koncertu sklidila ohromný úspěch. Další den Kevin objevil ve schránce K dopisů. Mezi všemi nudnými úředními dopisy jeden vyčníval. Byl navoněný a na obálce měl nakreslené růžové srdíčko. Ten si okamžitě přečetl. Byl od fanynky!

Takové dopisy Kevin nedostává každý den. Obsah dopisu si tak hned slovo od slova zapamatoval. Bohužel pak při cestě do školy pršelo a dopisy Kevinovi zmokly. Některé se staly téměř nečitelnými. I tak se ale snažil a přečetl z nich, co jen šlo. Posloupnosti těchto znaků si zapsal. Nyní by chtěl vědět, který z těchto dopisů by mohl být oním dopisem se srdíčkem.

Tvar vstupu: Na prvním řádku vstupního souboru bude zadán text původního dopisu, jehož délka bude nejvýše 300 000 znaků. Na druhém řádku bude zadáno číslo K udávající celkový počet doručených dopisů (1 ≤ K ≤ 50). Na každém ze zbylých K řádků bude posloupnost maximálně 300 000 znaků, které se Kevinovi z daného dopisu podařilo přečíst. Všechny znaky dopisů budou složeny z malých a velkých písmen anglické abecedy a znaků ., ,, _, kde _ odděluje jednotlivá slova.

Tvar výstupu: Vypište K řádků výstupu. Na i-tý řádek umístěte řetězec ANO, pokud i-tý dopis může být oním dopisem se srdíčkem. To znamená, že i-tý dopis lze z původního dopisu vytvořit vynecháním některých znaků. V opačném případě vypište řetězec NE.

Ukázkový vstup:
Horoucne_Te_miluji,_Kevine.
5
Horoucne_Te_milujeme,_Kevine.
nemiluji
MILUJI.
Hor___eve.
Horce_Te_miluji,Kene.
Ukázkový výstup:
NE
ANO
NE
ANO
ANO

Řešení


26-Z1-4 Hroch v jezeře (12 bodů)


Praktická CodExová úlohaKevin po odpoledních hraje počítačovou hru Hroch v jezeře. Ve hře plave s hrochem ve velkém jezeře, ze kterého se tu a tam vynořuje ostrůvek. Některé ostrůvky jsou pusté, na jiných se nachází hroší laskominy – jídlo všeho druhu. Cílem hry je doplavat s hrochem na ostrůvek s co největším množstvím jídla a mezitím nevylézat z vody.

Ostrov je souvislá oblast políček pevniny, kde políčka považujeme za spojená, pokud se dotýkají hranou (nikoliv pouze rohem). Hroch může plavat nahoru, dolů, doleva a doprava.

Tvar vstupu: Na prvním řádku vstupu dostanete čísla SR udávající šířku a výšku mapy hry. Na každém z dalších R řádků bude S znaků, přičemž:

  • . znamená, že na políčku je voda,
  • # znamená, že na políčku je pevnina bez jídla,
  • J je pevnina s jídlem,
  • H je políčko, kde hroch začíná.

Zaručujeme, že na vstupu bude právě jedno políčko se znakem H.

Tvar výstupu: Na výstup napište jediné celé číslo udávající největší množství jídla na ostrově, ke kterému se hroch může ze své startovní pozice doplavit povolenými způsoby bez toho, aby mezitím vystoupil z vody.

Ukázkový vstup:
10 8
.J##..#.J#
..###.J#.J
#JJJ#..#.J
..###..J.J
.......#.J
.J.H.###.J
.J...#JJ.#
.J#..#JJ.J
Ukázkový výstup:
6

K této úloze jsme na Dnu otevřených dveří MFF UK ukázali drobnou nápovědu. Abychom byli spravedliví k ostatním, kteří třeba na DODu být nemohli, můžete se podívat na video se záznamem z přednášky.

Zbylé dvě úlohy této série jsou teoretické. K těmto úlohám je třeba vymyslet algoritmus a slovně ho popsat – tedy primární část řešení není zdrojový kód v nějakém programovacím jazyce, ale slovní popis. Sepsanou úlohu odevzdej opět na našem webu.

Řešení


26-Z1-5 Úkol z geometrie (12 bodů)


Kevin a jeho spolužáci dostali na hodině geometrie následující úkol. Mají zadaných N bodů na ose x. Je třeba každé dva po sobě jdoucí body spojit horní půlkružnicí. Kevin se podíval na posloupnost ze zadání a začal přemýšlet, jestli se některé dvě půlkružnice protnou. Navrhněte co nejefektivnější algoritmus, který pro zadanou posloupnost N bodů odpoví ANO, pokud se některé půlkružnice protínají, a NE, pokud nikoliv.

Na prvním obrázku je příklad pro posloupnost 0,8,20,14,18 a na druhém pro posloupnost 0, 12, 4, 10, 20. V prvním se kružnice neprotínají, v tom druhém protínají.

První ukázka Druhá ukázka

Řešení


26-Z1-6 Nezbední skřítci (14 bodů)


Kevin byl na vánočních trzích a co nesehnal – opravdové, živé vánoční skřítky! Tomu nemohl odolat a hned si jich N koupil. Dokonce byl každý jinak velký.

Vánoční hrocho-elf

Aby mu neutekli, vyrobil si pro ně doma řadu N klícek a každého do jedné zavřel. Zavření skřítci ale dělali příšerný kravál a neustále si stěžovali, že vedle sebe nemají podobně velké kamarády, se kterými by si mohli povídat.

Tak se Kevin rozhodl, že je v klíckách seřadí podle velikosti. Pro pořádek vždy vyndá jen dva skřítky a vymění jejich pozice.

Navrhněte algoritmus, který má Kevin použít, aby skřítky seřadil podle velikosti od nejmenšího po největšího na co nejméně prohození.

Příklad: Pokud máme tři skřítky zavřené v klíckách v pořadí: 3, 1, 2 (čím větší číslo, tím větší skřítek), tak je můžeme seřadit na dvě prohození. Nejdříve prohodíme skřítka 3 se skřítkem 1 a poté skřítky 32.

Řešení