První série začátečnické kategorie třicátého prvního ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 10. prosince v 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


Praktická opendata úloha31-Z1-1 Zuzka a poník (8 bodů)


Kevinova mladší sestra Zuzka má ráda zvířata, nejraději z nich koně. Rodiče ji proto přihlásili do jezdeckého oddílu. Kevin byl zvědavý, jak to tam probíhá, a proto se na jeden trénink přišel podívat.

Zuzka si osedlala jednoho z poníků, vylezla na něj a rozeběhla se s ním po cvičné kruhové dráze. Když ji proběhli asi potřetí, začal Kevin přemýšlet, jestli poník s přibývajícím časem zrychluje, nebo zpomaluje. Proto si vzal do ruky stopky a začal Zuzce odměřovat časy jednotlivých kol. Protože ale neumí stopky vynulovat, potřeboval by teď spočítat, jak dlouhé vlastně každé kolo bylo.

Tvar vstupu: Na prvním řádku se nachází počet kol N. Na dalších N řádcích máte vždy zapsaný čas na stopkách na konci kola. Čas je v digitálním formátu, např. 00:03:12 označuje 3 minuty a 12 sekund od začátku měření.

Tvar výstupu: Vypište N řádků, na každém řádku bude počet sekund, které jedno kolo trvalo.

Ukázkový vstup:
3
00:03:13
00:06:52
00:10:02
Ukázkový výstup:
193
219
190

Praktická opendata úloha31-Z1-2 Ukradený jezdec (10 bodů)


Když se sourozenci večer vrátili z tréninku, začal Kevin zkoumat úlohu, kterou jim zadal učitel matematiky. Týkala se toho, jak přesunout figurku mezi dvěma zadanými poli na šachovnici tak, aby se vždy pohybovala pomocí platných tahů jezdce – tedy vždy o dvě pole svisle nebo vodorovně a potom ještě o jedno pole kolmo. Navíc musí přesun zvládnout na nejmenší počet tahů.

Zuzka si všimla, jak nad tím Kevin přemýšlí, a řekla si, že ho pozlobí. Vzala mu figurku jezdce a utekla s ní ven! Kevin ji nejdřív chtěl dohnat, ale pak si řekl, že by radši mohl zkusit úlohu vyřešit i pro jiné figurky, než je jezdec.

Tvar vstupu: Na prvním řádku dostanete číslo N, což je rozměr šachovnice (počet řádků a sloupců). Na druhém řádku dostanete souřadnice pole, kde se nachází figurka, na třetím řádku souřadnice pole, kam máte figurku dopravit. Souřadnice jsou vždy určeny dvěma čísly, kde první číslo představuje sloupec a druhé řádek, počítáme od nuly (takže rozsah je od 0 do N-1).

Na dalším řádku dostanete počet povolených tahů T, na dalších T řádcích jsou pak zadány jednotlivé povolené tahy, každý opět pomocí dvou čísel – počet řádků a počet sloupců, o které můžete figurku v jediném tahu posunout.

Tvar výstupu: Vypište nejkratší cestu figurky: na první řádek počet potřebných tahů Q, na dalších Q-1 řádků souřadnice polí, která figurka po cestě navštíví. Souřadnice počátečního a cílového pole nevypisujte.

V příkladu máme zadané povolené tahy jezdce.

Ukázkový vstup:
8
3 1
6 3
8
1 2
2 1
-1 2
-2 1
1 -2
2 -1
-1 -2
-2 -1
Ukázkový výstup:
3
4 3
5 5
Ilustrační obrázek ze zadání

Praktická opendata úloha31-Z1-3 Průnik kvádrů (10 bodů)


Zuzka se nakonec přece jen s ukradenou figurkou vrátila. Dostala ve škole domácí úkol z geometrie – v rovině má nakreslených několik obdélníků a má za úkol spočítat plochu jejich průniku. Úloha ale neobsahuje náčrt, místo toho je každý obdélník zadaný pomocí intervalové notace: ta popisuje rozsah plochy, kde se obdélník nachází, pomocí intervalů. Například obdélník zadaný intervaly [1,3], [2,5] má levý spodní bod na souřadnicích [1,2] a pravý horní roh na souřadnicích [3,5].

Zuzka si chtěla překreslit všechny obdélníky na papír, ale přijde jí to moc zdlouhavé, a tak poprosila o pomoc Kevina. Chtěla by navíc vyřešit těžší variantu úlohy, kdy má spočítat průnik kvádrů v trojrozměrném prostoru.

Tvar vstupu: Na prvním řádku dostanete počet zadaných kvádrů N, následujících N řádků pak obsahuje jejich popisy. Každý kvádr je zadaný pomocí šesti celých čísel X0, X1, Y0, Y1, Z0, Z1, což znamená, že se nachází na intervalech [X0, X1], [Y0, Y1] a [Z0, Z1]. Máte jistotu, že levý okraj intervalu je vždy ostře menší než pravý.

Tvar výstupu: Vypište jediné číslo: objem průniku všech kvádrů. Je možné, že průnik je prázdný, pak je odpověď 0.

Obrázek odpovídá příkladu: první kvádr je šrafovaný vodorovně, druhý svisle, třetí je vyznačen světle šedou barvou. Průnik je zvýrazněn tmavě šedou barvou.

Ukázkový vstup:
3
0 4 0 3 0 2
2 4 0 5 0 2
3 4 0 7 1 2
Ukázkový výstup:
3
Ilustrační obrázek ze zadání

Praktická opendata úloha31-Z1-4 Piškvorky naslepo (12 bodů)


Stejně jako každý rok, i teď Kevin ve škole pořádá velký turnaj v piškvorkách. Má ale pocit, že tentokrát by herní systém potřeboval nějak oživit, protože hrát obyčejné piškvorky pořád dokola je přece jenom nuda.

Napadlo ho, že finalisté z jednotlivých tříd by mohli hrát slepé piškvorky: v této variantě soupeři při hře nevidí na čtverečkovaný papír, místo toho rozhodčímu v každém tahu řeknou souřadnice místa, kam chtějí položit svůj symbol.

Tvar vstupu: Dostanete počet tahů N, potom na dalších N řádcích zadaný vždy symbol (křížek nebo kolečko) a celočíselné souřadnice místa, kam byl položen. Každý tah je korektní, nestane se, že bychom chtěli umístit symbol na již obsazené pole.

Tvar výstupu: Vypište na jeden řádek symbol hráče, který vyhrál (umístil pět symbolů do nějakého řádku, sloupce nebo diagonály) a číslo tahu, kdy k tomu došlo (číslujeme od nuly), např. X 18. Pokud nikdo nevyhrál, vypište NIKDO.

Ukázkový vstup:
4
X 0 1
O 0 2
X 2 2
O 2 1
Ukázkový výstup:
NIKDO

Teoretická úloha31-Z1-5 Fotka zastupitelů (12 bodů)


Ani městu, v němž bydlí Kevin, se nevyhnuly podzimní komunální volby. Nově zvolení zastupitelé města si na první schůzi udělali společnou oficiální fotografii, na níž stojí vedle sebe v jedné řadě.

Kevin píše o volbách článek do školních novin a chce v něm fotku použít. Protože je ale široká, potřebuje ji oříznout. Aby nebyl podezírán z toho, že nějaké straně nadržuje, nesmí se v oříznuté části vyskytovat dva zastupitelé, kteří by pocházeli ze stejné politické strany. Kevina zajímá, jaké nejširší oříznutí může použít.

Trochu formálněji – máte k dispozici posloupnost celých čísel. Najděte v této posloupnosti nejdelší souvislý úsek, v němž se žádné číslo nevyskytuje dvakrát (všechna jsou unikátní). Například pro posloupnost 1 2 0 2 3 4 3 je to úsek 0 2 3 4. Pokud by existovalo více nejdelších úseků, vypište libovolný z nich.


Teoretická úloha31-Z1-6 Trasa demonstrací (14 bodů)


Kvůli výsledkům voleb se ve městě rozmohly politické nepokoje. Téměř všechny strany naplánovaly protestní průvody proti programům svých oponentů. Každý takový průvod začne na okraji města, a to na nějakém významném místě (nádraží, památník, …) a potom projde ulicemi na nějaké jiné významné místo, taktéž na okraji města, kde akce skončí. Městská policie má ale pořádný důvod k obavám: všechny protestní průvody jsou naplánované na stejný den! Strážníci chtějí trasy průvodů upravit takovým způsobem, aby se žádné z nich nemohly potkat, protože jinak by mohlo dojít k násilí.

Máte zadanou mapu města jako spoustu křižovatek, propojených ulicemi. Pro jednoduchost předpokládáme, že mezi každou dvojicí křižovatek existuje jen jediná cesta. Takové struktuře se říká strom a můžete si o ní přečíst v naší kuchařce pro začátečníky.

Je naplánováno N protestních průvodů. V mapě města je 2N okrajových křižovatek označených jako významné. Naplánujte každý protestní průvod tak, aby začal na nějaké významné křižovatce, prošel aspoň jednou ulicí, skončil v jiné významné křižovatce a nemohlo dojít k tomu, že by se na libovolné křižovatce potkal s nějakým jiným průvodem.

Příklad mapy města s N = 2 vidíte na obrázku, významné křižovatky jsou značeny šedě. Jediným možným řešením je to, že první průvod půjde z křižovatky A přes B, C a D do E, druhý průvod z F přes G a H do I.

Ilustrační obrázek ze zadání