Čtvrtá 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: 4. května 2015 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-Z4-1: Záhada Pražského orloje
- 27-Z4-2: Unavení u oken
- 27-Z4-3: Běžkaři v Praze!
- 27-Z4-4: Koňské skoky
- 27-Z4-5: Poškolní trest
- 27-Z4-6: Příprava grilovačky
Úvodem vás chceme upozornit na nové články o načítání vstupu v Pythonu a jazyce C v naší webové Encyklopedii. Mohly by vám být nápomocné při řešení praktických úloh.
27-Z4-1 Záhada Pražského orloje (8 bodů)
Sára, Kevinova dobrá kamarádka, má velký zájem v kultuře, zvlášť pak v architektuře. Kevin se jí rozhodl udělat radost a domluvil se svým známým prohlídku Pražského orloje zevnitř. Sára z prohlídky byla celá nadšená a do detailů se na všechno vyptávala, zatímco Kevina tyto řeči moc nebraly a více jej zaujala ozubená kolečka, která byla všude kolem. Zvlášť dvě do sebe zasazená, která se pravidelně každou vteřinu pootočila. Jedno mělo dohromady A zubů a druhé B zubů.
Jeden zub na prvním kolečku byl označen křížkem a stejně tak jedna zdířka druhého kolečka. Kevin si všiml, že tyto křížky se pravidelně setkávají. Zajímalo by ho, za jak dlouho se to stane.
Tvar vstupu: Na prvním řádku vstupu dostanete číslo N udávající počet dotazů. Na každém z dalších N řádků se pak nacházejí čísla A a B udávající velikosti koleček. 1 ≤ A,B ≤ 1 000 000 a N ≤ 5 000.
Tvar výstupu: Na výstup vypište pro každý dotaz jedno číslo udávající dobu, po které se obě značky na kolečkách setkávají.
3 3 6 12 27 4 17
6 108 68
27-Z4-2 Unavení u oken (10 bodů)
Když se Kevin jednoho dne vracel z florbalového tréninku, byl hodně, ale opravdu hodně zničený. Tentokrát už nevydržel jít dál a musel si na sídlišti sednout na lavičku. Jak tam tak unavený seděl, zahleděl se do svítících oken paneláku naproti. Ten byl H pater vysoký a v každém měl W oken.
Seděl, civěl a skoro usínal, když v tom se najednou z vedlejší lavičky ozval Petrův hlas: „Taky počítáš svítící okna? Já se tím po tréninku vždycky nejvíc odreaguju!“ „Jo?“ odpovídá vylekaně Kevin. „Kolik je jich asi nejvíce spojených dohromady?“ pokračuje zaujatě Petr.
Tvar vstupu:
Na vstupu na prvním řádku dostanete dvě čísla oddělená mezerou 1 ≤ W, H
≤ 1 000. Na dalších H řádcích pak bude vždy W znaků '.' nebo
'#', kde '.' značí zhasnuté okno a '#' značí rozsvícené okno.
Tvar výstupu: Na výstup vypište jedno číslo udávající velikost největší souvislé svítící plochy (v počtu svítících oken). Dvě svítící okna považujeme za sousední, pokud jsou buďto přímo nad sebou, nebo přímo vedle sebe. Za spojená nepovažujeme okna sousedící pouze přes roh.
6 3 #.#.## ##.#.# ##.###
7
27-Z4-3 Běžkaři v Praze! (10 bodů)
A je to tady! Do Prahy dorazilo 20 kamiónů se sněhem a můžou se tam uspořádat běžkařské závody. Sněhu ale nebylo dost, a tak se organizátorům povedlo vyrobit jen jeden okruh dlouhý S kilometrů s jednou dráhou. No jo, jak ale teď změřit čas všem K závodníkům? Když jeden druhého dožene, tak už jej pak nemá jak předjet, a tedy jeho naměřený čas bude špatný.
Organizátoři vymysleli následující systém. Fixně určí pořadí závodníků a budou je pravidelně po 1 minutě pouštět na trať a v cíli měřit čas. Pokud závodník dojede v těsném závěsu za jiným, tak se jeho čas počítat nebude a pojede pak znova. Jinými slovy vyškrtnou ze startovního listiny všechny závodníky, u kterých již naměřili správný čas a zbytek si závod zopakuje.
Kevin zná všechny závodníky a pro každého závodníka i ví, jakou stálou rychlostí vi jezdí. Při znalosti těchto hodnot je možné spočítat, kolik závodů dohromady bude muset proběhnout. Kolik?
Tvar vstupu: Na vstupu na prvním řádku dostanete počet závodníků K a délku tratě S v kilometrech. Na druhém řádku budou čísla v1, … , vK udávající rychlosti závodníků v kilometrech za hodinu v pořadí, v jakém za sebou startují.
1 ≤ K ≤ 10 000, 1 ≤ S ≤ 1 000, 1 ≤ vi ≤ 100.
Tvar výstupu: Na výstup vypište jediné číslo udávající, kolikrát musí závod proběhnout, aby byl všem závodníkům čas změřen správně.
4 10 2 3 5 4
3
Poznámka: Na většinu vstupů by měla stačit přesnost na sekundy (tedy když závodníci doběhnou v jiné sekundě, nemusí se druhý posílat na trať znovu, jinak ano). Naše referenční řešení však počítá výsledky úplně přesně (dokonce bez nutnosti práce s desetinnými čísly – ano, jde to) a je možné, že pro některé vstupy budete tuto přesnost potřebovat také. Zkuste to :-)
27-Z4-4 Koňské skoky (12 bodů)
Malé Zuzce, Kevinově sestřičce, už je 5 let a Kevin ji začal učit hrát šachy. Zuzka všechny figurky docela chápe, ale dělá jí problémy správně skákat koněm. Na to jí Kevin vymyslel následující cvičení. Postavil jí na šachovnici 5 stejných černých koní a označil jí 5 cílových pozic, do kterých s nimi má doskákat. Jejím úkolem je přesunout koně do cílové pozice na co nejméně skoků. Aby pro ni úkol nebyl příliš těžký, tak během toho může postavit více koní na stejné políčko.
Tvar vstupu: Na vstupu na prvním řádku bude číslo N udávající rozměr šachovnice. 5 ≤ N ≤ 5 000. Na dalších pěti řádcích jsou vždy dvě čísla určující x-ové a y-nové souřadnice koní (indexujeme od nuly, tedy pozice 0…N-1). Na posledních pěti řádcích jsou opět dvě čísla určující x-ové a y-nové souřadnice cílových pozic. Jednotlivé pozice na vstupu se mohou libovolně opakovat.
Tvar výstupu: Na výstup vypište jedno celé číslo udávající nejmenší počet skoků, kterými je možné se dostat ze startovní do cílové pozice. Jakýkoliv kůň může doskákat na jakoukoliv cílovou pozici, na pořadí nezáleží.
První: Druhý: 9 14 6 1 7 7 2 2 6 4 6 5 5 7 2 6 0 1 3 7 5 3 8 2 10 3 5 3 12 5 3 3 7 11 7 8 9 5 1 8 0 6
První: Druhý: 8 13
27-Z4-5 Poškolní trest (12 bodů)
Kevin dostal čtyřku z písemky z dějepisu. Už zase. To ho pěkně naštvalo a celou písemku roztrhal na malinké kousíčky. Dosáhl tak uspokojivého pocitu zadostiučinění. Alespoň do chvíle, kdy paní učitelka chtěla písemky vybrat zpátky. Kevin je poslušný hoch, tak písemku bez odmlouvání paní učitelce vrátil a vysloužil si tím dvě hodiny po škole.
Tam paní učitelce musel pomáhat se tříděním papírů. Dostal jednu hromadu papírů očíslovaných na přeskáčku čísly 1 až N. Jelikož je líný, chtěl by to udělat následujícím způsobem: V každém kroku buď vzít vrchní, nebo spodní papír původní hromádky a položit jej na vršek, nebo spodek výstupní hromádky (která je na začátku prázdná). Po vás by chtěl navrhnout algoritmus, který pro zadanou hromadu papírů rozhodne, zda je, či není možné ji takovým způsobem setřídit.
Příklad: Hromadu papírů 2, 3, 4, 1 setřídit lze, zatímco hromadu 6, 4, 5, 2, 1, 3 setřídit nelze.
27-Z4-6 Příprava grilovačky (14 bodů)
Kevin, Sára a Petr plánují uspořádat monstrózní grilovačku, na kterou pozvou všechny své spolužáky. To bude akce! Ale taky spousta práce. Musí připravit pozvánky, upéct maso, ale ještě předtím jej koupit a rozdělat oheň. Než rozdělají oheň, tak zas musí nasekat dříví a tak dále. Všechny povinnosti si sepsali a vyšel jim seznam s dohromady N činnostmi. Mezi ně si pak nakreslili šipky podle toho, jak na sobě závisí. Například z pečení masa vede šipka na koupení masa a na rozdělání ohně a z rozdělání ohně vede šipka na nasekání dřeva.
Nyní se dohadují, v jakém pořadí jednotlivé činnosti nejlépe plnit. Jinými slovy chtějí najít takové pořadí vykonávání činností, aby před plněním konkrétní činnosti již určitě byly splněné všechny činnosti, na kterých daná činnost závisí. Navrhněte pro ně algoritmus, který takové pořadí najde, a nebo rozhodne, že žádné takové neexistuje.
