|  |
Soutěž v programování 2000
Hokejový šampionát
Vážení soutěžící,
pro toto kolo soutěže ACM programming contest se budeme zabývat
hokejem, jehož popularita po včerejším postupu Česko-slovenska výrazně
stoupla (mimochodem, nevíte s kým ti Čechoslováci budou hrát to finále?).
Jistě jste si všimli, že se závěrečných turnajů Mistrovství světa účastní
v posledních letech stále častěji méně známé země, které nepatří zrovna
k hokejovým velmocem. Jednou z nich je i Núbijská republika, do které
nedávno přicestoval slavný jugoslávský trenér Stojan Jakotič a pokouší se
vybudovat reprezentační mužstvo. Vaším úkolem je pomoci mu s některými
rutinními úkoly.
Všechny programy, které máte vytvořit, budou číst vstupní data ze
standardního vstupu a výsledky zapisovat v předepsané formě
na standardní výstup. Pokud není stanoveno jinak, jsou všechna
čísla na vstupu volena tak, aby se vešla do standardního typu
integer v Pascalu nebo int v Céčku.
Doufáme, že řešení těchto úloh bude pro vás znamenat přínos i jinde
než v oblasti matematické informatiky a sportu.
Přejeme vám mnoho úspěchu při soutěži.
Jedním z největších favoritů letošního MS v hokeji je tým Núbije pod
vedením nejlepšího jugoslávského trenéra Stojana Jakotiče. Tento
trenér sice dokáže přimět své svěřence k úžasným výkonům, ale nevyzná
se v núbijských zvycích. Núbijské zvyky jsou navíc velmi složité.
Jistě chápete, že pokud chce Stojan trénovat núbijské mužstvo, musí
žít jako správný núbijec.
Proto mu tým núbijských sociologů vytvořil plán, co a v jakém oblečení
má během dne dělat. Pro každou akci je v plánu zaveden zvláštní symbol.
Tak například plán:
-([3+(*y*)$])/
znamená: Vstaň, obleč si triko, obleč si kalhoty, pozdrav, nasnídej se, vem si boty, běž trénovat, zuj si boty, navečeř se, svlékni si kalhoty, svlékni si triko, běž spát.
Jistě uznáte, že takový plán je velice nepřehledný a proto by Núbijci potřebovali vytvořit program, který zkontroluje jeho správnost. Důležité je hlavně aby si Stojan svlékal věci v opačném pořadí, než v jakém si je oblékl. Například pokud si obleče napřed triko a pak svetr, musí si nejdříve svléci svetr a pak teprve triko. Takové pravidlo platí v Núbiji pro všechno oblečení. Pokud si tedy oblékne svetr a na něj boty, musí nejprve zout boty, a pak svetr. Další velmi důležitá věc je, aby na konci plánu, před tím než jde Stojan spát, na sobě nic neměl. Jednotlivé páry symbolů pro oblékání a svlékání jsou:
( )
[ ]
{ }
< >
(* *)
Dva znaky '(*' musí být interpretovány jako jeden symbol, ne jako '(' následovaná hvězdičkou, analogicky '*)'. Kombinace '(*)' musí být chápána jako '(*' následovaná ')'.
Specifikace vstupu
První řádek obsahuje celé kladné číslo N, 1 <=N <=100000. Dále následuje N zadání. Každé zadání je na jednom řádku. Na řádce není více než 3000 znaků.
Specifikace výstupu
Pro každý správný plán vypište řádek obsahující 'Plan je v poradku.'. Pro každý nesprávný plán vypište 'V planu je chyba.'.
Příklad vstupu
2
(*a++(*)
(*a{{+}}*)
Příklad výstupu
V planu je chyba. Plan je v poradku.
Během minulého mistrovství světa se vyskytl problém. Lidé kteří přišli na utkání pozdě, se nemohli dostat na svá místa v hledišti. Bránili jim v tom diváci kteří přišli již dříve a byli tak zažráni do sledování hry, že se nechtěli zvedat ze sedadel. Protože na to organizátoři nebyli připraveni, nevěděli, jak celou situaci vyřešit. Letos se kvůli účasti núbijského týmu očekává ještě větší návštěvnost. Navíc, protože většina občanů Núbije nevlastní hodinky, budou Núbijci chodit pozdě. Organizátoři se proto rozhodli použít k umísťování pozdě chodících návštěvníků moderní technologii. Vaším úkolem je zhotovit pro ně program. Vstupem programu bude mapa obsazených sedadel a místo, odkud budou přicházet diváci. V tomto místě může, ale nemusí být volné sedadlo. Program musí spočítat, kolik sedadel je možné z tohoto místa obsadit. Diváci se při zaplňování volných sedadel mohou pohybovat pouze v horizontálním nebo vertikálním směru. Pohyb v diagonálním směru není povolen.
Specifikace vstupu
Vstup se skládá z N zadání. První řádek vstupu obsahuje pouze celé kladné číslo N. Dále následují jednotlivá zadání. První řádek obsahuje čtyři kladná čísla w, h, x a y, 1 <=w, h <=100, 1 <=x <=w, 1 <=y <=h, kde w je šířka hlediště, h je výška hlediště, x vodorovná pozice vchodu, počítáno od jedné od levého okraje, a y je svislá pozice od horního okraje hlediště. Dále následuje h řádků o w znacích. Znak '.' reprezentuje prázdné sedadlo, zatímco znak '#' představuje obsazené sedadlo.
Specifikace výstupu
Pro každé zadání program vytiskne řádek ve tvaru `Do hlediste se vejde X divaku.', kde X je počet diváků, kteří mohou z daného vchodu zaplnit část hlediště.
Příklad vstupu
2 3 3 1 2 ... ### ##. 10 10 2 2 ########## #........# #........# #........# #........# #........# #........# #........# #........# ##########
Příklad výstupu
Do hlediste se vejde 0 divaku. Do hlediste se vejde 64 divaku.
Pro snazší rozbor hry zakoupilo núbijské hokejové družstvo kameru, která snímá shora hrací plochu.
Při analýzách předchozích her se totiž ukázalo, že stejné situace mají i stejné pokračování. Je proto výhodné využít hledání podobnosti při analýze hry. Obdobné je to i u situací, které jsou zrcadlovým obrazem nebo otočením již známé situace.
Napište program, který pro dva snímky hrací plochy určí, zda jsou situace na nich podobné. Podobná situace může vzniknout některou z těchto transformací:
- shoda
- otočení o 90o po směru hodinových ručiček
- otočení o 180o po směru hodinových ručiček
- otočení o 270o po směru hodinových ručiček
- zrcadlení podle horizontální osy
- zrcadlení následované otočením (podle pořadí výše)
Specifikace vstupu
První řádek vstupu je celé číslo N, udávající počet zadání. Dále následují jednotlivá zadání. Každé zadání se skládá z řádky o jednom čísle R (2<=R<=10) udávajícím velikost vzoru a R řádků. Každý řádek obsahuje R znaků '.' (tečka) nebo 'x' (řádek původního vzoru), mezeru a druhých R teček a 'x'ek (řádek transformovaného vzoru).
Specifikace výstupu
Pro každé zadání vypiště jednu řádku obsahující jednu z těchto odpovědí: 'Shoda', 'Otoceni o X stupnu', kde X je '90', '180' nebo '270', 'Zrcadleni', 'Zrcadleni a otoceni o X stupnu', případně 'Ruzne vzory'.
Příklad vstupu
4 5 x...x ....x .x... ...x. ...x. .x... ..x.x ..x.. ....x xx..x 2 x. xx x. xx 4 ..x. ...x xx.. .... .... xx.. ...x ..x. 4 .x.. ..x. .x.x x... .... ..xx ..x. ....
Příklad výstupu
Otoceni o 90 stupnu Ruzne vzory Zrcadleni Zrcadleni a otoceni o 270 stupnu
Každý trenér musí zpětně sledovat a rozebírat hru svého mužstva. Bohužel, v celé Núbii existuje pouze jediný videorekordér, který patří prezidentovi a je tedy pro trenéra velmi těžko dostupný. Situace nasnímané pomocí kamery (viz úloha Kamera) tedy obvykle již nikdo nestuduje, neboť získat povolení prezidentovy ochranky není snadné. Trenéru Jakotičovi tedy nezbývá, než poučení z odehraných zápasů získávat pomocí statistického rozboru poměru střel, přesilovek a podobně. Tyto statistické rozbory však jsou velmi matematicky náročné, proto je třeba napsat program, který bude sloužit jako jednoduchá kalkulačka umožňující vypočítat jednoduché výrazy.
Specifikace vstupu
Na vstupu je celé číslo N, N >=1. Následuje N zadání. Každé zadání je na samostatném řádku ve formátu `axb', kde a a b jsou celá kladná čísla, 1 <=a, b <=10000, a x je jeden ze znaků `+', `-', `*', `/'.
Specifikace výstupu
Pro každé zadání, které se dá beze zbytku vypočítat, napište `Vysledek je X.', kde X je výsledek výrazu. Pokud při operaci dělení vychází nenulový zbytek, napište `Vysledek je X, zbytek Y.', kde Xje podíl a Y je zbytek. Zbytek musí být samozřejmě kladný a menší než dělitel.
Příklad vstupu
5 1+2 1-4 3*3 15/3 18/4
Příklad výstupu
Vysledek je 3. Vysledek je -3. Vysledek je 9. Vysledek je 5. Vysledek je 4, zbytek 2.
Jak jistě víte, núbijskou reprezentaci trénuje slavný jugoslávský trenér Stojan Jakotič. Protože Stojan ještě dostatečně nezná své núbijské svěřence, neví, jak je nasazovat při hře. Rozhodl se proto vyzkoušet při tréninku všechny možnosti. Během mistrovství bude nasazovat pouze osvědčené kombinace hráčů. Tato metoda se ukázala být velmi užitečná. Některé sestavy se totiž vůbec neosvědčily. Hlavním důvodem bylo to, že útočníci měli s chytáním nepřekonatelné problémy. Brankářům zase vadila při útoku výstroj.
Protože má Stojan Jakotič krátkou paměť a nepamatuje si, které kombinace hráčů vyzkoušel, potřebuje vaši pomoc. Vaším úkolem je napsat program, který vytiskne všechny kombinace hráčů. Trenér si potom tento soupis bude nosit na tréninky a odškrtávat si jiz vyzkousené varianty.
Specifikace vstupu
Vstup se skládá z N zadání. První řádek vstupu obsahuje pouze celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání je tvořeno dvěma řádky. První řádek obsahuje číslo K, 6<=K<=20, na druhém řádku je K různých čísel hráčů oddělených mezerou v pořadí od nejmenšího po největší.
Specifikace výstupu
Pro každé zadání program vytiskne všechny možné šestice hráčů, každou na jedné řádce. Čísla v každé šestici musí být uspořádána od nejmenšího k největšímu. Všechny šestice (řádky) musí být uspořádány lexikograficky, to znamená napřed seřazeny podle prvního, potom podle druhého čísla atd., stejně jako je to uvedeno v příkladu výstupu. Každé zadání (včetně posledního) musí být ukončeno prázdným řádkem.
Příklad vstupu
2 7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34
Příklad výstupu
1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 1 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 13 21 1 2 3 5 13 34 1 2 3 5 21 34 1 2 3 8 13 21 1 2 3 8 13 34 1 2 3 8 21 34 1 2 3 13 21 34 1 2 5 8 13 21 1 2 5 8 13 34 1 2 5 8 21 34 1 2 5 13 21 34 1 2 8 13 21 34 1 3 5 8 13 21 1 3 5 8 13 34 1 3 5 8 21 34 1 3 5 13 21 34 1 3 8 13 21 34 1 5 8 13 21 34 2 3 5 8 13 21 2 3 5 8 13 34 2 3 5 8 21 34 2 3 5 13 21 34 2 3 8 13 21 34 2 5 8 13 21 34 3 5 8 13 21 34
Núbijská vláda se rozhodla, že do dalšího MS vyšle také svoji hokejovou reprezentaci. Jelikož v Núbii nemají ledovou plochu, rozhodli se improvizovat. Ušlapali v poušti čtverec rozdělený na 8x8 polí, na kterém bude hrát 8 hráčů.
Na této ploše núbijské mužstvo zkouší různé taktiky. Každé pole písečné plochy je ohodnoceno podle jeho příznivosti pro budoucí vývoj hry. Aby hráči dobře viděli na všechny strany, nesmí se na stejném řádku, sloupci ani jakékoli diagonále, vyskytovat dva hráči. Taktika je tím úspěšnější, čím větší je součet ohodnocení pozic hráčů.
Specifikace vstupu
Na prvním řádku je celé kladné číslo N. Dále následuje N zadání. Každé zadání se skládá z osmi řádků, na každém řádku je osm celých kladných čísel menších než 100, vyjadřujících ohodnocení políček hrací plochy.
Specifikace výstupu
Pro každé zadání vypište na výstup větu 'Nejlepsi ohodnoceni je X.', kde X je ohodnocení nejúspěšnější taktiky.
Příklad vstupu
2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1
Příklad výstupu
Nejlepsi ohodnoceni je 260. Nejlepsi ohodnoceni je 9.
Jedním z členů núbijské reprezentace je také oblíbenec národa Venca Nedopita. Venca má kromě hokeje řadu dalších zájmů, bohužel se ted během šampionátu pohroužil do knihy o záhadách matematiky a nemůže se od ní odpoutat.
Pro úspěch hokejistů je však nezbytné, aby se tým zcela věnoval přípravě na nastávající těžké zápasy. Nyní se Venca věnuje problému tzv. spřátelených čísel a celé dny stráví jejich hledáním. Pomůžete mu v jeho snaze?
Dvojice spřátelených čísel je taková dvojice čísel, kde jedno je součtem
dělitelů druhého a naopak. Součet dělitelů čísla je součet všech jeho dělitelů
(včetně jednicky) s výjimkou sebe sama.
Př.: 284 a 220.
284:
1 + 2 + 4 + 71 + 142 = 220
220:
1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
Napište program, který po přečtení dvou čísel rozhodne, zda jsou spřátelená nebo ne.
Specifikace vstupu
První řádek obsahuje celé kladné číslo N, 1<=N<=200000. Dále následuje N zadání. Každé zadání reprezentuje řádek se dvěma celými kladnými čísly X, Y oddělenými mezerou 1<=X,Y<=10000.
Specifikace výstupu
Pro každé zadání vypište větu 'Venco, dobry!', pokud jsou čísla spřátelená, jinak vypište větu 'Venco, smula.' .
Příklad vstupu
2 284 220 1280 1786
Příklad výstupu
Venco, dobry! Venco, smula.