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

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

• Termín série: 24. února 2014 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

• 26-Z2-1: Had z domina
• 26-Z2-2: SADO
• 26-Z2-3: Šifrovaná zpráva
• 26-Z2-4: Životně důležitá úloha
• 26-Z2-5: Nedopité skleničky
• 26-Z2-6: Čtecí hlavy

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-Z2-1 Had z domina (8 bodů)

Kevinova malá sestra Zuzka dostala k Vánocům domino. Zatím ho neumí hrát, tak kostky jenom skládá do různých tvarů. Úplně nejraději z nich staví tlustého hada – vezme N kostek, postaví je do jedné dlouhé řady a přikládá je k sobě delší stranou.

Se svým výtvorem se přišla pochlubit Kevinovi. Toho ale víc než had zajímala samotná čísla na něm. V hadovi by chtěl otočit právě jednu kostku o 180° tak, aby první i druhý řádek hada měly sudý součet. Kolika způsoby toho může dosáhnout?

Tvar vstupu: Na prvním řádku dostanete číslo N udávající délku hada, kterého Zuzka vytvořila (1 ≤ N ≤ 1 000). Na dalších dvou řádcích bude na každém N čísel z rozmezí 0 až 9 oddělených mezerou.

Tvar výstupu: Na výstup vypište jedno celé číslo K udávající, kolik je možností, jak otočit právě jednu kostku tak, aby byl součet v obou řádcích sudý.

6
1 2 4 9 2 3
3 7 3 2 1 3

4

5
2 3 1 3 4
2 1 2 7 8

0

Řešení

26-Z2-2 SADO (10 bodů)

Společně s Kevinem, Sárou a Petrem jdete na týmovou matematickou soutěž jménem SADO. Hned na začátku jste dostali následující úlohu a ostatní po vás chtějí její řešení.

Kolik celých čísel z uzavřeného intervalu [a,b] je dělitelných číslem x a zároveň číslem y?

Tvar vstupu: Na vstupu dostanete na jednom řádku čtyři celá čísla a,b,x,y oddělená mezerou (1 ≤ a ≤ b ≤ 10¹⁵, 1 ≤ x,y ≤ 10⁹).

Tvar výstupu: Na výstup vypište jedno celé číslo, které bude odpovědí na výše položenou otázku.

1 90 3 5

6

Řešení

26-Z2-3 Šifrovaná zpráva (10 bodů)

Nezbednice Sára už zase lelkuje ve škole. Místo toho, aby dávala pozor, píše šifrovanou zprávu pro Kevina. Nejdříve z písmen anglické abecedy a bez mezer napíše původní zprávu, pak každé písmeno nahradí jiným. Stejná písmena jsou vždy nahrazena stejně a různá písmena jsou naopak vždy nahrazena různými písmeny. Takové šifře se obvykle říká jednoduchá substituce.

Po vás by chtěla zkontrolovat, zda někde neudělala chybu. Dostanete text původní zprávy a jeho zašifrovanou podobu a máte ověřit, že každé dva stejné znaky se zašifrují na stejný znak a každé dva různé na různý znak.

Tvar vstupu: Na prvním řádku vstupu bude číslo N udávající délku zprávy (1 ≤ N ≤ 10⁶). Na druhém řádku dostanete původní zprávu složenou z N velkých písmen anglické abecedy. Na třetím, posledním, řádku dostanete zašifrovanou zprávu složenou také z N velkých písmen anglické abecedy.

Tvar výstupu: Pokud zpráva není zašifrovaná správně, vypište na jediný řádek výstupu slovo NE. Pokud je zašifrovaná správně, na první řádek vypište slovo ANO a na druhý vypište bez mezer 26 znaků, které budou udávat, na co se zašifrují která písmena ze vstupu.

První bude udávat, na co se zašifruje písmeno A, druhý, na co se zašifruje písmeno B a tak dále, až poslední bude udávat, na co se zašifruje písmeno Z. U písmen, která se v původní zprávě nevyskytují, si můžete vybrat libovolně. Stále však musíte dodržet, že se různá písmena zašifrují různě.

18
AHOJKEVINEJAKSEMAS
XOBNKYWZCYNXKAYFXA

ANO
XDEGYHIOZNKJFCBLPQARSWMTUV

Řešení

26-Z2-4 Životně důležitá úloha (12 bodů)

Kevinovi se po silvestrovské noci zdál fakt divný sen. Byl vsazen do přísně střeženého žaláře a odsouzen k vyhladovění. Krutý to osud! Naštěstí ale svítala naděje, v rohu byl malý nenápadný poklop vedoucí ke svobodě. K jeho otevření ale bylo potřeba zadat na číselném zámku odpověď na následující úlohu.

Máme zadanou posloupnost N celých čísel. Prvek má v posloupnosti aritmetický výskyt, pokud se v ní vyskytuje pravidelně. To znamená, že pokud si vezmeme indexy jeho výskytů v posloupnosti, tak tyto indexy tvoří aritmetickou posloupnost, tj. rozdíl každých dvou po sobě jdoucích indexů je stejný. Tomuto rozdílu se říká diference.

Vypište ve vzestupném pořadí všechny prvky, které mají v posloupnosti aritmetický výskyt, a navíc ke každému z nich i jeho diferenci. Pokud se prvek v posloupnosti vyskytuje pouze jednou, má aritmetický výskyt s diferencí 0.

Tvar vstupu: Na vstupu na prvním řádku dostanete délku posloupnosti N (1 ≤ N ≤ 10⁵). Na dalších N řádcích budou jednotlivé prvky posloupnosti v rozmení -10⁹ až 10⁹.

Tvar výstupu: Na první řádek výstupu vypište počet prvků K, které mají v posloupnosti aritmetický výskyt. Na dalších K řádků vypište ve vzestupném pořadí jednotlivé prvky. Každý řádek bude obsahovat hodnotu prvku, mezeru a jeho diferenci.

6
1
2
3
2
3
3

2
1 0
2 2

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-Z2-5 Nedopité skleničky (12 bodů)

Kevin se celý vyděšený probudil, opláchl se vodou a šel do kuchyně. Tam na stole našel řadu N nedopitých skleniček šampaňského. Je to divné, ale skleničky byly seřazeny podle toho, kolik v nich ještě zbývalo, a v lahvi navíc bylo dalších K mililitrů šampaňského. To by chtěl Kevin nalít právě do jedné ze skleniček tak, aby se hladinou co nejvíce přiblížil jiné skleničce. Do které skleničky jej má nalít?

Jinými slovy: Vaším úkolem je v setříděné posloupnosti najít dvě čísla (nemusí být nutně těsně za sebou), jejichž rozdíl se co nejvíce blíží číslu K. Navrhněte co nejefektivnější algoritmus, který tato čísla najde. Pokud existuje více takových dvojic, stačí nalézt libovolnou z nich.

Řešení

26-Z2-6 Čtecí hlavy (14 bodů)

Kevin od tatínka dostal dlouhou magnetickou pásku s několika vyznačenými místy a k tomu čtecí hlavy. Každá čtecí hlava jezdí nad páskou a dokáže z ní číst informace. Hlava v každém kroku může buď stát na místě, popojet o jedno políčko doleva, anebo popojet o jedno políčko doprava. Pak přečte informaci z políčka, kde zrovna je, a celý postup se opakuje.

Zároveň je na pásce N míst, která chceme pomocí hlav přečíst. Máte zadané souřadnice míst k přečtení a počáteční souřadnice hlav. Na kolik nejméně kroků lze všechny zadané segmenty přečíst?

Úkol 1 [5b]

Čtete pomocí jedné hlavy.

Úkol 2 [9b]

Čtete pomocí dvou hlav.

Navrhněte co nejefektivnější algoritmus na spočítání minimálního potřebného počtu kroků. Efektivitu algoritmu počítejte vzhledem k hodnotě N, případně k velikosti pásky. Můžete předpokládat, že políčka, kde hlavy stojí na začátku, jsou již přečtené.

Poznámka: Tato úloha je velmi podobná úloze 26-2-7 z hlavní kategorie KSP, kde se však řešila pro obecný počet hlav. Pro jednu nebo pro dvě hlavy existuje jednodušší a efektivnější algoritmus na spočítání minimálního počtu kroků, než je ten popsaný v řešení odkazované úlohy.

Řešení