Třetí série začátečnické kategorie třicátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
- Termín série: 16. dubna 2018 v 8:00, praktické úlohy lze za třetinu bodů odevzdávat až do 23. dubna 2018
- 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
- 30-Z3-1: Rozkolísaná produktivita
- 30-Z3-2: Podlézání Číňanům
- 30-Z3-3: Teambuilding
- 30-Z3-4: Korporátní seznamka
- 30-Z3-5: Schůze vedoucích
- 30-Z3-6: Těžce zasloužená dovolená
Body získané v této sérii (a předchozích dvou) vám mohou pomoci se dostat na jarní soustředění KSP, které se bude konat 12.-19. 5. v Horní Sytové u Jilemnice.
30-Z3-1 Rozkolísaná produktivita (8 bodů)
„Pojďte pracovat do naší společnosti a získejte programátorské zkušenosti už během studia!“ hlásal veselý barevný e-mail, který Kevinovi před měsícem přistál ve schránce. Proč bych do takovéhle nabídky nešel? pomyslel si tehdy Kevin. Ze školy do budovy Korporace, od které pocházela náborová zpráva, to je jenom pár kroků. Nějaké zkušenosti z reálného světa se hodí a peníze koneckonců taky…
Jenže teď už tam Kevin pracuje měsíc a k nějakému programování se takřka nedostal. Místo toho dostal za úkol šmírovat zaměstnance Korporace a hlídat jejich produktivitu, která může být i záporná (třeba pokud udělají nějakou chybu). Co je tohle za práci? Kupodivu firmu vůbec nezajímá, kolik práce kdo celkově odvede, místo toho nechce, aby produktivita zaměstanců příliš kolísala. To by totiž mohlo být známkou blížícího se infarktu.
Budeme se teď zabývat jen jedním zaměstnancem. Kevin si za každý den sledování zapsal celé číslo, které označuje úroveň pracovníkovy produktivity. V této řadě musí najít dvě čísla, pro která platí, že druhá mocnina jejich rozdílu je největší možná.
Na prvním řádku vstupu máte zadaný počet dní, kdy Kevin zaměstnance sledoval, na druhém řádku následují hodnoty produktivity, oddělené mezerou. Najděte dvě hodnoty s největší druhou mocninou rozdílu a vypište na výstup jejich pozice (první číslo je na pozici nula).
8 5 4 2 3 0 -1 1 2
0 5
30-Z3-2 Podlézání Číňanům (10 bodů)
Kevinovi se úspěšně podařilo uchránit několik pracovníků před nervovým zhroucením, jenže nazítří se málem zhroutil zase on, to když si ho do kanceláře pozval jeho vedoucí. „Brzy sem přijedou nějací kolegové z Číny. Vedoucí té výpravy se dokonce učí česky. Jenže je z čínštiny celý popletený a občas neví, jestli číst český text zleva, nebo zprava.“
„No a co my s tím?“ nechápavě se ptal Kevin. „Zařídíme mu lepšího učitele?“ „Nechci, aby se u nás v Korporaci ztrapnil při čtení nápisů. Takže projdeš všechny velké nápisy, co máme na chodbě, a zařídíš, aby se zleva doprava četly stejně, jako zprava doleva.“ „Vždyť ten text pak přestane dávat smysl!“ zhrozil se Kevin, ale vedoucího se mu přesvědčit nepodařilo.
Na vstupu dostanete jednoslovný text tvořený písmeny anglické abecedy: na prvním řádku bude délka textu, na druhém text samotný. Máte dovoleno vzít nějaké písmeno a zaměnit ho za jiné. Rozmyslete si, jak lze na nejmenší počet takovýchto operací vytvořit palindrom – tedy text, který se jak zleva doprava, tak zprava doleva čte stejně. Na první řádek výstupu vypište počet operací, na druhý řádek výsledné slovo. Existuje-li více řešení, vypište libovolné.
15 jednacimistnost
5 tednasimisandet
30-Z3-3 Teambuilding (10 bodů)
Jak setkání s Číňany dopadlo, Kevin nevěděl, protože nebyl v práci. Vedoucí se ale tvářil spokojeně a nabídl Kevinovi, aby se zúčastnil víkendového firemního teambuildingu.
Právě teď se Kevin s několika kolegy z práce nachází v nějakém potemnělém bludišti. Stojí v centrální místnosti a podle mapy, kterou obdrželi, vychází z této místnosti paprskovitě několik chodeb. V bludišti se nachází tři kategorie věcí: dveře, klíče a dolary.
Existuje několik druhů dveří, každé z nich lze otevřít pouze klíčem stejného druhu. Od každého druhu se v bludišti nachází právě jedny dveře a právě jeden klíč. V bludišti se také nachází dolary: máme za úkol jich sesbírat co nejvíce. Platí, že na začátku se nacházíme v centrální místnosti. Podívejte se na příklad bludiště (odpovídá příkladu vstupu a výstupu níže):
Na prvním řádku dostanete počet chodeb C, vedoucích
z centrální místnosti, a počet dvojic dveře-klíč D. Následuje C řádků, na
každém z nich je popis jedné chodby. Ten je tvořen jedním číslem
udávajícím délku chodby Li a poté Li čísly popisujícími obsah chodby v
pořadí od centrální místnosti.
Nula znamená dolar, K > 0 označuje dveře druhu K a K < 0 klíč druhu -K. Druhy dveří a klíčů jsou očíslovány od 1 do D.
Vypište, kolik dolarů můžeme celkem nasbírat.
4 5 4 0 -1 0 -2 5 2 1 0 -3 0 4 3 4 -5 0 3 5 -4 0
4
30-Z3-4 Korporátní seznamka (12 bodů)
Kevin si musel přiznat, že takovýhle teambuilding ho vlastně docela bavil. On i jeho kolegové se pozdě večer unaveni dostali na chatu, kde byli ubytováni. Ale až tady se ukázalo, že uvnitř není dostatečné množství postelí pro všechny a že někteří zaměstnanci budou muset zalehnout do spacáků. Ležet na zemi se nikomu nechtělo a o postele se strhl boj.
Vedoucí navíc dostal další ze svých „skvělých“ nápadů. Na teambuilding jeli zaměstanci ze dvou různých oddělení a vedoucí si usmyslel, že ještě teď v noci udělá seznamovací párty, aby se všichni lépe poznali. Někteří zaměstanci, ať už z prvního, nebo z druhého oddělení, si ale demonstrativně lehli do postelí, které si stihli zabrat, a řekli, že už z nich do rána nevylezou.
Co teď chudákovi vedoucímu zbývá? Možná tak svolat zbylé zaměstance a rozmístit je do postelí tak, aby každý z nich měl možnost seznámit se s někým z druhého oddělení.
V ubytovně se nachází jedna dlouhá řada N postelí. Některé postele jsou prázdné, jiné jsou obsazeny zaměstnanci oddělení A, jiné zaměstnanci oddělení B. Vedoucí chce zaplnit všechny prázdné postele, a to tak, aby nikdy nedošlo k tomu, že tři zaměstnanci stejného oddělení spí vedle sebe. Je možné, že pro nějaké počáteční obsazení nelze tuto podmínku splnit. Předpokládejte, že z každého oddělení se teambuildingu účastní alespoň N zaměstnanců, takže se vedoucí nemusí bát, že mu při určování míst zaměstanci nějakého oddělení „dojdou“.
Na vstupu dostanete řetězec složený z písmen A, B a podtržítek. Vaším úkolem
je nahradit podtržítka za písmena A nebo B tak, aby se nikde nevyskytovala
tři stejná písmena vedle sebe. Vypište upravený řetězec, případně slovo
NEEXISTUJE, pokud řešení neexistuje.
AA_B_A_BA
AABBAABBA
30-Z3-5 Schůze vedoucích (12 bodů)
Dřív než se vedoucímu podařilo najít řešení předchozí úlohy, Kevin usnul. Ráno u snídaně si všiml, že je vedoucí nějaký nervózní. Zeptal se lidí, se kterými seděl u stolu, co se to vlastně včera stalo. Ale nikdo nevěděl.
Na začátku dalšího týdne, kdy se všichni vrátili zpět do práce, generální ředitel Korporace oznámil, že chce uspořádat mimořádné setkání všech vedoucích. Těm se k němu ale najednou moc nechtělo a začali se ošívat, že nemají moc času. Každý z nich nabídl jen jeden možný časový interval, kdy má čas na jednání. Ředitel by tedy aspoň chtěl uspořádat schůzku v momentě, kdy má čas co nejvíce vedoucích.
Máte N vedoucích. Každý z nich si dokáže udělat čas na schůzi v nějakém intervalu [A,B], kde A, B ∈R. Zjistěte, jaké největší množství vedoucích se může dohromady u ředitele potkat, a o jaký interval (intervaly) konkrétně půjde.
30-Z3-6 Těžce zasloužená dovolená (14 bodů)
Vedoucí se sešli u ředitele, který je obvinil z toho, že z firmy odsávali peníze. O víkendu si totiž v neformálním prostředí Kevinův vedoucí pustil pusu na špacír a vysvětlil zaměstancům druhé firmy, jak si vydělává na dovolenou. Na konci měsíce musí svému nadřízenému odeslat všechny peníze, které vydělali jeho podřízení. Jenže než to udělá, tak si část těchto peněz „ulije“ na svůj vlastní účet. K řediteli se tahle zpráva dostala. A co hůř, vypadá to, že si tímhle způsobem přivydělávají, až na ředitele samotného, úplně všichni!
Hierarchie firmy vypadá takto: máme jediného generálního ředitele, ten má nějaké množství podřízených zaměstnanců, každý tento zaměstanec může mít zase svoje vlastní podřízené… a tak dále, dokud na konci nejsou řadoví pracovníci, kteří žádné podřízené nemají.
Pro každého zaměstance známe kladnou celou částku označující, kolik peněz zvládne vydělat za rok. Na konci roku všechny peníze putují k řediteli tímto způsobem: pracovníci bez podřízených vezmou vydělanou částku a pošlou ji svému nadřízenému. Ten shromáždí částky od podřízených, přidá peníze, které vydělal sám, a všechno to pošle svému nadřízenému. Tak to pokračuje dál, až všechny vydělané peníze získá generální ředitel.
Jenže v posledních letech se ve firmě rozmohlo podvádění. Jakýkoliv zaměstanec, než pošle svoje peníze nadřízenému, se teď podívá, kolik jich vlastně má u sebe. Pokud je to více nebo rovno číslu D (to je pro všechny zaměstnance stejné), tak si D peněz převede na svůj osobní účet a dál předá jenom zbylou částku. Za převedené peníze si pak koupí luxusní dovolenou v Karibiku.
Máte zadanou hierarchii zaměstanců: o každém zaměstnanci víte, kdo je jeho nadřízený (právě jeden zaměstnanec žádného nadřízeného nemá), a částku, kterou vydělá. K tomu ještě obdržíte číslo D. Zjistěte, kolik zaměstanců podvede firmu a odjede na dovolenou.
Na obrázku vidíte příklad hierarchie. Šedou barvou jsou vyznačeni zaměstnanci, kteří jedou na dovolenou, pokud D = 9. U generálního ředitele vydělanou částku nemáme, pro naše zadání není relevantní.
