|  |
|
Katedra počítačů ČVUT FEL & Czech ACM Chapter Soutěž v programování 1998 Rodina OkurkovýchVážení soutěžící, pro toto kolo soutěže ACM programming contest jsme pro vás připravili několik praktických úloh, s nimiž se musí potýkat rodina Okurkových. Kromě hlavy rodiny, Toníka Okurky, poznáte také jeho krásnou ženu Julii, nezbedného syna Toníčka a hravou dceru Amálku. Všechny programy, které máte vytvořit, mají čí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 přejeme vám mnoho úspěchu při soutěži. Organizátoři Mince(název programu: mince.c, mince.p, mince.C) Toníkova prababička byla šetrná paní a své nemalé úspory uložila do zlatých mincí. Před svou smrtí pak tyto mince spravedlivě rozdělila mezi své vnuky a vnučky. Tak dostal Toník jednu zlatou minci. Protože samotné minci by mohlo být smutno, nechal si Toník vyrobit několik přesných napodobenin. Napodobeniny byly vyrobeny tak precizně, že je od pravé mince nelze pohledem rozeznat. Bylo tedy třeba uchovávat pravou minci odděleně od napodobenin. Jednoho dne půjčil Toník všechny mince Amálce na hraní a ta je promíchala. Toníka teď čeká nelehký úkol: najít pravou minci. Naštěstí ví, že všechny napodobeniny mají stejnou hmotnost a že hmotnosti napodobeniny a pravé mince se liší. Dále má k dispozici přesné váhy a závaží o hmotnostech 1, 2, 2, 5, 10, 20, 20, 50, 100, 200, 200, 500 a 1000 gramů. Hmotnosti napodobeniny i pravé mince jsou celočíselným násobkem hmotnosti nejmenšího závaží. Vaším úkolem je napsat program, který pro zadaný počet mincí určí, jaký nejmenší počet vážení Toníkovi vždy stačí k tomu, aby nalezl pravou minci a určil, zda je pravá mince těžší či lehčí než její napodobenina. Jedním vážením se rozumí jedno porovnání hmotností obsahů obou misek vah. Na obě misky je možné dát libovolné množství mincí i závaží. Specifikace vstupuVstup 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 jedním řádkem. Na tomto řádku je uvedeno pouze jedno celé číslo K, K > 2, které znamená počet zkoumaných mincí (včetně té pravé). Specifikace výstupuPro každé zadání program vytiskne jeden řádek "Minimalni pocet vazeni je X.", kde za X se dosadí minimální počet vážení, který je nutný k rozpoznání pravé mince. Příklad vstupu2 12 3 Příklad výstupuMinimalni pocet vazeni je 3. Minimalni pocet vazeni je 2. Reversi(název programu: reversi.c, reversi.p, reversi.C) Toníkova dcera Amálka je hravé děvče a protože hraní s panenkami ji už dávno nebaví, hraje s kamarádkami důmyslnou hru Reversi. Reversi je hra určená pro dva hráče. Hrací plocha obsahuje 8 x 8 políček, do každého políčka lze podle určitých pravidel umístit nejvýše jeden žeton. Žeton je z jedné strany bílý, z druhé černý. Jeden hráč umísťuje žetony do hrací plochy bílou stranou nahoru, druhý bílou stranou dolu.
Hráč může položit žeton pouze do prázdného políčka a navíc pouze tehdy, "přebarví-li" alespoň jeden žeton protihráče. K přebarvení dojde, jestliže souvislá linie žetonů hráče, který nehrál, se umístěním žetonu stala obklopena žetony protihráče (jeden z obklopujících žetonů musí být ten, který byl právě položen na hrací plochu) a v takové situaci se všechny žetony této linie otočí (tzn. změní barvu). Za souvislou linii se považují sousední žetony umístěné vodorovně, svisle nebo diagonálně. Při položení žetonu se vždy přebarvuje maximální možný počet žetonů. Obrázek ukazuje příklad, kdy v pozici nalevo byl položen žeton O na pozici [7,3]. Po přebarvení soupeřových žetonů vznikne situace zobrazená na obrázku vpravo. Hráči se v pokládání žetonů střídají. Nastane-li situace, kdy některý z nich nemůže táhnout tak, aby přebarvil alespoň jeden žeton protihráče, je na tahu znovu druhý hráč. Amálka by ráda měla program, který by mohla využít ve školním turnaji v této hře. Vaším úkolem je napsat tento program. Specifikace vstupuVstup 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í se skládá z popisu hrací plochy, označení hráče, který je na tahu, a seznamu příkazů, které má program provést. Hrací plocha je popsána osmi řádky, z nichž každý obsahuje osm znaků. Znak v i-tém řádku a v j-tém sloupci popisuje stav políčka se souřadnicemi [i,j] (řádky i sloupce číslujeme od jedné). K popisu stavu políčka jsou použity tyto znaky:
Jako označení hráče, který je na tahu, je použito písmeno 'X', nebo písmeno 'O'. Seznam příkazů jsou příkazy uváděné vždy na samostatném řádku a zakončené příkazem 'Q'. Povolené příkazy:
Specifikace výstupuPro každé zadání vypíše program řádek "Hra c. C:", kde za C se dosadí pořadové číslo zadání. Zadání se číslují vzestupně od jedné. Dále program pro každý zadaný příkaz vypíše odpovídající výstup. Výstupy pro jednotlivé příkazy jsou:
Příklad vstupu2 -------- -------- -------- ---XO--- ---OX--- -------- -------- -------- X L M35 C L D Q XXXXO--- XXXO---- XXO----- XO------ -------- -------- -------- -------- O L M25 C L M67 D Q Příklad výstupuHra c. 1: 35,46,53,64 Hrac O: 1, hrac X: 4 34,36,56 -------- -------- ----X--- ---XX--- ---OX--- -------- -------- -------- Hra c. 2: Zadny legalni tah. Hrac O: 3, hrac X: 12 35 Neplatny tah. XXXXO--- XXXXX--- XXO----- XO------ -------- -------- -------- -------- Lodě(název programu: lode.c, lode.p, lode.C) Julie čte zajímavou vědecko-fantastickou knihu, v níž hlavní hrdinka potřebuje vyřešit problém, jak co nejvýhodněji využívat vesmírné nákladní lodě. Lodě mají přepravovat předměty ve tvaru D-dimenzionální mřížky, jejichž rozměr v každé dimenzi je 3. V uzlech mřížky jsou koule jednotkové váhy. Mezi uzly vedou spojnice, jejichž hmotnost je vzhledem k hmotnosti koulí zanedbatelná. Váha každého předmětu je tedy rovna počtu jeho uzlů. Cena každého předmětu je rovna součtu počtu uzlů a počtu spojnic. Každá loď má určitou nosnost a my chceme přepravu organizovat tak, aby při každé jízdě měl náklad maximální cenu.
Vaším úkolem je napsat program, který pro zadanou nosnost určí, kolik předmětů a jaké dimenze je třeba naložit, aby cena těchto předmětů byla maximální. Předpokládejte, že máte k dispozici neomezený počet kusů od každého předmětu. Specifikace vstupuVstup 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 jedním řádkem, na němž je jedno celé nezáporné číslo K, K <= 10000000, které určuje nosnost lodě. Specifikace výstupuPro každé zadání program vytiskne jeden řádek "Xm Xm-1 ... X1 X0", kde Xm > 0 a Xi, 0 <= i <= m je počet předmětů i-té dimenze, které je třeba naložit, aby cena naložených předmětů byla maximální. Příklad vstupu4 1 100 175 9841 Příklad výstupu1 1 0 2 0 1 2 0 1 1 1 1 1 1 1 1 1 1 1 1 Výlet(název programu: vylet.c, vylet.p, vylet.C) Julie miluje pěší výlety do hor. Také Toník dříve rád vyrážel za sněhem a sluncem, často vybaven jen ešusem, lžící a spacákem. Jak léta ubíhala, uvykali oba postupně pohodlnému životu ve dvou místnostech svého panelákového bytu. Teď už se jen neradi vzdávájí pohodlí, jež nabízí luxusní otoman po babičce či dřevěná lavice z doby husitské. Asi vás proto nepřekvapí, že si chtějí vzít na výlet co možná nejvíce věcí. Zbývá vyřešit otázku, kdo tyto věci ponese. Této otázce věnovali spoustu zimních večerů a po dlouhých diskuzích se dohodli na kompromisu: shromáždí věci, které si chtějí vzít s sebou, u každé věci zjistí její hmotnost, a pak si věci rozdělí v určitém poměru. Vaším úkolem je napsat program, který jim zodpoví otázku, zda lze vybrané věci rozdělit na dvě množiny tak, aby součty hmotností věcí v každé z množin byly přesně v zadaném poměru. Specifikace vstupuVstup 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. Na prvním řádku jsou tři celá kladná čísla X, Y, Z, 1 <= X <= 200, 1 <= Y,Z <= 100. Na druhém řádku je X celých kladných čísel, která udávají hmotnosti jednotlivých vybraných věcí. Čísla jsou navzájem oddělena mezerou. Žádné z těchto čísel není větší než 500. Specifikace výstupuPro každé zadání program vytiskne jeden řádek. Pokud lze vybrané věci rozdělit na dvě množiny tak, aby poměr součtů hmotností v každé z množin byl Y:Z, bude výstup "Ano.", v opačném případě bude výstup "Ne.". Příklad vstupu3 10 1 1 1 1 1 1 1 1 2 2 2 2 5 2 2 3 3 3 3 3 6 2 5 1 2 3 4 5 6 Příklad výstupuAno. Ne. Ano. Tchyně(název programu: tchyne.c, tchyne.p, tchyne.C) Toník je vášnivý cyklista a často podniká výlety do míst blízkých i vzdálenějších. V poslední době však již neusedá na kolo s takovou chutí a nadšením jako dříve. Příčinou této změny je jeho tchyně, která se rozhodla, že jej bude na každé jeho cyklistické vyjížďce doprovázet. Umíte si asi představit tu radost a nadšení, jež se zrcadlily v Tondových očích poté, co mu tchyně sdělila svoje rozhodnutí. Naštěstí mu můžete pomoci. Po několika výletech totiž Tonda zjistil, že tchyně je po nastoupání určitého počtu metrů tak vyčerpaná, že není schopna pokračovat v jízdě. Proto zvolil tuto organizaci společné vyjíždky: on i tchyně vyjedou ze stejného bodu a každý sám se dopraví na předem určené místo srazu. Vaším úkolem je napsat program, který Tondovi pomůže určit, zda tchyně může dojet na místo srazu či nikoliv. Specifikace vstupuVstup se skládá z N zadání. První řádek vstupu obsahuje pouze celé kladné číslo N. Dále následují jednotlivá zadání. Na prvním řádku každého zadání jsou rozměry obdélníkové mapy R a C, 1 <= R,C <= 100. Následuje R řádků, z nichž každý obsahuje C čísel. Číslo na i-té pozici v j-tém řádku udává nadmořskou výšku bodu o souřadnicích [i,j]. Souřadnice levého horního rohu mapy jsou [1,1]. Body jsou spojeny cestami, které tvoří pravoúhlou mřížku. Cesta mezi dvěma sousedními body vede vždy pouze do kopce, nebo pouze z kopce, nebo po rovině. První řádek, který následuje po definici mapy, obsahuje pouze číslo T, které udává počet metrů, jež je tchyně schopna maximálně nastoupat. Další řádek obsahuje pouze čtyři čísla R1, C1, R2, C2. Čísla jsou navzájem oddělená mezerou. R1, C1 jsou souřadnice výchozího bodu a R2, C2 jsou souřadnice místa srazu. Specifikace výstupuPro každý dotaz program vytiskne jeden řádek textu. Pokud tchyně může dojet na místo srazu, vytiskne "Tchyne muze dojet.", v opačném případě vytiskne "Tchyne nedojede.". Předpokládejte, že tchyně jezdí pouze po cestách. Příklad vstupu2 3 3 1 2 3 2 3 2 3 2 1 1 1 1 3 3 6 5 1 2 3 4 5 9 8 7 6 5 1 2 3 4 5 1 9 9 9 9 7 5 5 5 5 1 1 1 1 1 8 1 1 6 2 Příklad výstupuTchyne nedojede. Tchyne muze dojet. Zlomky(název programu: zlomky.c, zlomky.p, zlomky.C) Malý Toník Okurka je ve věku, kdy děti ještě pravidelně navštěvují základní školu. Většina z nich sice už dávno není přesvědčena o prospěšnosti takového počínání, nicméně z různých důvodů do školy alespoň občas docházejí. Vždyť uznejte, že např. kouřit někde sám daleko za městem je nesrovnatelné s tím, když si zapálíte cigaretu za přítomnosti spolužáků na školním záchodku. S malým Toníčkem má však paní učitelka jiné trápení. Docházení do školy mu sice nečiní velké potíže, horší je to ale s tím, jak jej ve škole udržet v klidu. Protože je to neposeda, vymyslela si na něj paní učitelka tuto lest: každé ráno dostane Toník několik příkladů na počítání se zlomky a musí zůstat ve škole, dokud je všechny nevyřeší. To se Toníkovi moc nelíbí, protože spíše než zlomky jej zajímá poslední verze Kernel Hacker's Guide a nejnovější číslo Playboye. Proto by rád měl program, který za něj příklady vyřeší. Vaším úkolem je tento program napsat. Specifikace vstupuVstup 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é na jednom řádku. Každé zadání se skládá z výrazu, kde výraz je
Výrazy se vyhodnocují zleva doprava a uplatňují se standardní priority operátorů. Po provedení každé dílčí operace je možné mezivýsledek reprezentovat jako podíl dvou celých čísel, z nichž se obě vejdou do standardního typu integer v Pascalu a int v Céčku. Specifikace výstupuPro každé zadání program vytiskne jeden řádek "Vysledek je X.", kde za X se dosadí hodnota zadaného výrazu. Pokud je výsledek ve formě zlomku, musí být maximálně zkrácen (tj. čitatel i jmenovatel musí být nesoudělná čísla). Příklad vstupu7 9/19-4/19+2/19 2/3+1/3 +21/+20*-2/+3 +4/+5++5/+6 (3/4)/(5/7) 45/4/6/5/7 (10000/10000)*(10000/10000)*(10000/10000) Příklad výstupuVysledek je 7/19. Vysledek je 1. Vysledek je -7/10. Vysledek je 49/30. Vysledek je 21/20. Vysledek je 3/56. Vysledek je 1. Noty(název programu: noty.c, noty.p, noty.C) Toník není žádný velký muzikant. Má však hudbu rád, a proto se rozhodl, že se v ní zdokonalí. Za tímto účelem opouští pravidelně každý čtvrtek svoji krásnou ženu Julii a odchází do jedné z pražských garáží, aby zde vyluzoval zvuky ne zcela nepodobné hudbě. Jeho oblíbeným nástrojem je klavír. Protože ještě nezvládá akordy, doprovází zbytek orchestru alespoň samostatnými tóny. To, jaké tóny má Tonda hrát, se dozví vždy při zkoušce od kapelníka. Tondova paměť však trpí častými návštěvami restaurací 5. cenové skupiny, a tak si Tonda musí jednotlivé tóny zapisovat, aby je do přístí zkoušky nezapomněl. Tóny zapisuje jako řetězce složené ze znaků a, b, c, d, e, f, g, h. I přes Tondovu snahu se často stane, že mu v zápise nějaké tóny chybějí, či naopak přebývají. Nedávno při prohlídce osobních věcí zjistil, že vlastní dva takovéto tónové zápisy. Protože si není jistý tím, který z nich je ten správný, rozhodl se, že z obou zápisů vyškrtne minimální počet tónů tak, aby oba zápisy byly shodné. Tím dosáhne toho, že v zápise určitě nebudou žádné tóny špatně. Vaším úkolem je napsat program, který pro zadané dva tónové zápisy určí, jaký celkový nejmenší počet tónů je třeba vyškrtnout, abychom dostali dva shodné zápisy. Specifikace vstupuVstup 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í se skládá ze dvou řádků. Na každém z nich je jeden řetězec, který představuje jeden tónový zápis. Délka každého řetězce je nejméně 1 a nejvýše 1000. Specifikace výstupuPro každé zadání program vytiskne jeden řádek "Je treba vyskrtnout X tonu.", kde za X se dosadí minimální počet tónů, které je třeba vyškrtnout, aby zbylé řetězce byly shodné. Příklad vstupu2 abab bbabc cdacbed cdhacb Příklad výstupuJe treba vyskrtnout 3 tonu. Je treba vyskrtnout 3 tonu. Podnikatel(název programu: podnikatel.c, podnikatel.p, podnikatel.C) Malý Toník plánuje stát se podnikatelem a vydělat spoustu peněz. Protože nerad něco odkládá, začal již svůj sen uskutečňovat. Zatím zkoušel štěstí na střelnici u kolotočů, na hracích automatech a dokonce i při karetní hře Boží požehnání, lidově též Gotes. Bohužel, štěstí mu moc nepřálo, a tak jeho podnikání vykazuje ztrátu. Není ovšem všemu konec, neboť Toník objevil novou hazardní hru Master-Mind, která by mu mohla veškeré ztráty vynahradit. Dříve než však přistoupí na hru o peníze, chce se Master-Mind důkladně naučit. Za tímto účelem potřebuje program, který dokáže ohodnotit jeden pokus v této hře. Vaším úkolem je napsat tento program. Program dostane na vstupu dvě posloupnosti A1, A2, ... AM a B1, B2, ... BM. Jeho úkolem je určit počet míst, na kterých jsou v obou posloupnostech stejná čísla, a dále počet čísel, která se vyskytují v obou posloupnostech na různých místech. Nechť Z je množina takových dvojic (I,J), 1 <= I,J <= M, že AI = BJ a nechť pro každé dva různé prvky této množiny (I1,J1) a (I2,J2) platí, že I1 <> I2 a J1 <> J2. Potom označíme X(Z) počet takových prvků množiny Z, pro které I = J, a Y(Z) počet prvků, pro které I <> J. Nyní definujeme relaci uspořádání nad všemi možnými množinami Z takto: Z1 <= Z2 právě tehdy, když platí jedna z následujících dvou možností:
Úkolem programu je zjistit hodnoty X(Zmax) a Y(Zmax), kde Zmax je největší ve smyslu uvedené relace. Nazvěme X(Zmax) počet černých kolíčků a Y(Zmax) počet bílých kolíčků. Specifikace vstupuVstup 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 třemi řádky. Na prvním řádku každého zadání jsou dvě čísla M a K, 1 <= M,K <= 1000000. Hodnota M udává počet členů posloupnosti, K je maximální číslo, které se může v posloupnostech vyskytnout. Na druhém řádku každého zadání jsou čísla A1, A2 ... AM, navzájem oddělena mezerami. Na třetím řádku každého zadání jsou čísla B1, B2 ... BM, také navzájem oddělena mezerami. Specifikace výstupuPro každé zadání program vypíše řádek "Cernych: X, bilych: Y", kde za X se dosadí počet černých kolíčků a za Y se dosadí počet bílých kolíčků. Příklad vstupu3 5 3 1 2 3 1 2 2 3 1 2 3 1 2 1 2 9 9 1 2 3 4 5 6 7 8 9 2 3 1 4 5 6 8 9 7 Příklad výstupuCernych: 0, bilych: 4 Cernych: 0, bilych: 0 Cernych: 3, bilych: 6 |
