English Version English Version

ACM Programming Contest
kódování češtiny

Katedra počítačů ČVUT FEL & Czech ACM Chapter

Soutěž v programování 1998

Politická strana PSOS

V souvislosti s nadcházejícími volbami v ČR vzniklo několik nových politických stran. Jednou z těchto stran je i strana Programátoři za Stabilní Operační Systémy (PSOS), která jistě zaujme nejen originálními předvolebními sliby. Hlavní bod volebního programu PSOS je zřejmý z názvu strany, bylo by však chybné domnívat se, že je to bod jediný.

Protože chce strana PSOS uspět ve volbách co nejlépe, rozhodla se nasadit do předvolebního boje i výpočetní techniku. Z peněz zahraničních sponzorů byl zakoupen výkonný superpočítač optimalizovaný pro výpočty v předvolební kampani. Problém ovšem spočívá v programovém vybavení. Protože je celý projekt přísně tajný, není možné zadat tvorbu softwaru některé z renomovaných počítačových firem. Předsednictvo strany PSOS se tedy obrací na vás s žádostí o pomoc. Vaším úkolem je vytvořit sadu programů, která pomůže straně PSOS vyhrát volby.

Přejeme vám mnoho úspěchů.

Metrický čas

(název programu: cas.c, cas.p, cas.C)

Jedním z nejdůležitějších bodů volebního programu strany PSOS je také zavedení tzv. metrického času z důvodu mnohem snadnější manipulace v operačních systémech. Tím se tyto systémy stávají stabilnějšími, což je samozřejmě hlavním cílem strany.

Délka dne v metrickém času zůstává, ale ten se dále dělí na 10 metrických hodin (mhod), každá mhod na 100 metrických minut (mmin), každá mmin na 100 metrických sekund (msec). 10 metrických dnů (mden) tvoří metrický týden (mtyden), 10 metrických týdnů metrický měsíc (mmesic) a 10 metrických měsíců tvoří metrický rok (mrok). Na první pohled je zřejmé, že takové počítání času je mnohem výhodnější.

Některé opoziční strany však stále přicházejí s námitkami, že přechod na tento nový čas se neobejde zcela bez problémů. Předseda PSOS se rozhodl, že tyto námitky vyřeší jednou provždy tím, že vydá freeware program na převod mezi oběma druhy počítání času. Vaším úkolem je napsat část tohoto programu, převod z klasického (starého) počítání času na čas metrický. Metrické hodiny, metrické minuty a metrické sekundy se počítají stejně jako v klasickém tvaru od 0, metrické dny a metrické měsíce se počítají od 1. Existuje metrický rok 0. Při převodu času zaokrouhlujte metrické sekundy na celá čísla dolů. 0:0:0 1.1.2000 klasického času je 0:0:0 1.1.0 času metrického. Počítejte s tím, že klasický rok je přestupný, pokud je beze zbytku dělitelný čtyřmi. Výjimkou jsou roky, které jsou beze zbytku dělitelné stem - ty jsou přestupné pouze tehdy, pokud jsou zároveň dělitelné také čtyřmi sty. Tedy například roky 1996, 2400 a 2000 jsou přestupné, roky 1900, 2300 a 2002 nikoli.

Specifikace vstupu

První řádek vstupu obsahuje celé kladné číslo N, které udává počet zadání. Poté následuje přesně N nezávislých zadání. Každé zadaní je na jediném řádku ve tvaru "hodina:minuta:sekunda den.mesic.rok", kde hodina, minuta, sekunda, den, mesic a rok je čas a datum v klasickém tvaru. Omezení všech čísel je podle klasických pravidel pro datum, 2000 <= rok <= 50000.

Specifikace výstupu

Pro každé zadání vypište právě jednu řádku ve tvaru "mhod:mmin:msec mden.mmesic.mrok", kde mhod, mmin, msec, mden, mmesic a mrok je čas a datum v metrickém tvaru.

Příklad vstupu

7
0:0:0 1.1.2000
10:10:10 1.3.2001
0:12:13 1.3.2400
23:59:59 31.12.2001
0:0:1 20.7.7478
0:20:20 21.7.7478
15:54:44 2.10.20749

Příklad výstupu

0:0:0 1.1.0
4:23:72 26.5.0
0:8:48 58.2.146
9:99:98 31.8.0
0:0:1 100.10.2000
0:14:12 1.1.2001
6:63:0 7.3.6848

Foto

(název programu: foto.c, foto.p, foto.C)

Volební kampaň je v plném proudu, a proto se i strana PSOS rozhodla investovat nějakou tu miliardu do propagace. Nejmenovaný poslanec této strany přišel s originální myšlenkou, že by strana mohla voličům předhodit skupinovou fotografii jejich poslaneckého klubu. Avšak ani po mnoha mítincích, konferencích a zasedáních se poslanci nedokázali dohodnout, v jakém pořadí budou na fotografii stát. Když jim navíc jejich stranický fotograf sdělil, že se na fotografii všichni nevejdou, začalo být v kuloárech opravdu horko. Nakonec poslanci v tajném hlasování rozhodli, že problém vyřeší demokraticky - vyfotografují se ve všech možných variacích a na každé nástěnce či billboardu vystaví jinou fotografii. Jelikož byly v této souvislosti zaznamenány případy korupce, kdy se někteří poslanci snažili prosadit propagaci své vlastní osoby na úkor ostatních, rozhodlo vedení strany vnést do zmatku okolo fotografií pořádek. Každému poslanci bylo přiděleno jedinečné Identifikační Číslo (IČO), každá fotografie se tedy dala popsat posloupností IČO čísel. To umožnilo jednotlivé posloupnosti resp. fotografie uspořádat. Na množině posloupností (variací) stejné délky je definováno uspořádání takto: variace p je větší než variace q právě tehdy, když existuje i takové, že pj = qj pro každé j < i a pi > qi, kde xi je IČO i-tého poslance ve variaci x. Vaším úkolem je pro zadanou variaci r určit její pořadové číslo v takto uspořádané množině variací.

Specifikace vstupu

Vstupní soubor obsahuje na prvním řádku celé kladné číslo N, které udává počet zadání. Dále následuje N zadání. Každé zadání je tvořeno dvěma řádky. První řádek každého zadání obsahuje přirozená čísla n a k, 1 <= k <= n <= 12, kde n je celkový počet poslanců a k je počet poslanců, kteří se vejdou na jednu fotografii. Druhý řádek obsahuje k přirozených čísel z řady 1n (každé nejvýše jednou).

Specifikace výstupu

Pro každou úlohu vytiskněte text "Variace cislo I ma poradové cislo J.", kde I je číslo zadání (počítáno od 1) a J je pořadové číslo variace (počítáno také od 1).

Příklad vstupu

4
1 1
1
5 1
4
3 3
1 2 3
5 3
5 3 1

Příklad výstupu

Variace cislo 1 ma poradove cislo 1.
Variace cislo 2 ma poradove cislo 4.
Variace cislo 3 ma poradove cislo 1.
Variace cislo 4 ma poradove cislo 55.

Jeskyně

(název programu: jeskyne.c, jeskyne.p, jeskyne.C)

Před časem byl objeven rozsáhlý komplex jeskyní. Politická strana PSOS se to dozvěděla a aby si získala co nejvíce voličů, okamžitě zařadila do svého volebního programu, že tyto jeskyně zpřístupní veřejnosti.

Byla zde však jedna podstatná skutečnost, která této politické straně nějak unikla - komplex jeskyní je celý zaplavený. Protože si představitelé strany PSOS nechtěli udělat příliš velkou ostudu, začali přemýšlet, jak celou situaci vyřešit v případě, že volby vyhrají a budou muset své sliby plnit. Ve straně se ozývaly různé návrhy, jako např. zřídit u vchodu půjčovnu s potápěčskými potřebami nebo provozovat prohlídky malými ponorkami. Jako nejpravděpodobnější varianta se však jeví nechat vodu z jeskyní vyčerpat. Podzemní prostory jsou nyní dokonale zmapovány, to znamená, že se přesně ví, ve kterých místech je prostor zaplněný vodou. Naše strana by se ráda dozvěděla, kolik litrů vody bude muset vyčerpat, a tak shání šikovného programátora, který by pro ni vytvořil program pro výpočet tohoto množství vody na základě údajů o podzemních dutinách.

Prostory zaplněné vodou se skládají z krychlí o straně délky 1 metr. Lze pochopitelně vyčerpat pouze souvislé prostory (tzn. prostory tvořené sousedními krychlemi), které zasahují až do nejvrchnější vrstvy. Krychle jsou sousední, jestliže mají společnou jednu stěnu.

Specifikace vstupu

První řádek obsahuje celé kladné číslo N, 1 <= N <= 100000. Dále následuje N zadání. Každé zadání začíná řádkem, na kterém je trojice celých čísel XYZ oddělených mezerami, 1 <= X,Y,Z <= 100. Všechny zaplavené prostory jeskyně jsou uvnitř kvádru o stránách XYZ metrů. Na dalších řádcích je popsáno postupně Z vrstev jednotkových krychlí. Každá vrstva začíná řádkem s jediným číslem P, které určuje počet zaplavených krychlí v této vrstvě. Dále následuje P řádků, každý z nich obsahuje dvě čísla R a S, 1 <= R <= X, 1 <= S <= Y. Čísla R a S jsou souřadnice zaplavené krychle v metrech.

Specifikace výstupu

Pro každé zadání vypište na výstup jedinou větu "Je nutne vycerpat X litru vody.", kde místo X uveďte maximální množství vody v litrech, které lze vyčerpat, tedy velikost zaplavených prostor dostupných z vrchní strany jeskyně.

Příklad vstupu

2
4 4 5
1
3 3
2
1 2
3 3
4
1 2
2 2
2 3
3 3
2
3 3
1 1
0
3 7 2
1
2 4
5
1 4
2 3
2 4
2 5
3 4

Příklad výstupu

Je nutne vycerpat 8000 litru vody.
Je nutne vycerpat 6000 litru vody.

Kód

(název programu: kod.c, kod.p, kod.C)

Zasedací pořádek poslanců v parlamentu je ošemetná věc. Někteří chtějí sedět v předních řadách, protože je tam více světla, někteří v zadních řadách, protože je tam světla méně a více klidu, další touží především po tom, aby mohli sedět u okna. Navíc musí výsledný zasedací pořádek zůstat v naprosté tajnosti, aby nikdo nevěděl, kdo vedle koho sedí, protože vedle sebe sedící poslanci se mohou navzájem ovlivňovat. A tak, abychom neměli zmanipulovaný parlament, odhlasovali si poslanci, že jejich umístění se zakóduje Supertajným Kódem, který bude znát pouze několik spolehlivých supertajných agentů. Supertajný Kód délky n se značí SK(n), tvoří jej posloupnost všech různých binárních řetězců délky n a má tedy 2n prvků. Pro generování posloupnosti se používá následujícího rekurzivního algoritmu:

  • SK(1) = [0, 1]
  • SK(n) = 0.SK(n-1) + 1.REV{SK(n-1)}
Kde
  • [0, 1] je posloupnost skládající se ze dvou binárních řetězců délky 1, prvním z těchto řetězců je "0" a druhým "1".
  • b.SK(x) znamená kód, který vznikne z kódu SK(x) tak, že se před začátek každého řetězce v posloupnosti předřadí číslice b.
  • REV{SK(x)} znamená opačnou posloupnost než je SK(x), tedy poslední řetězec je první, předposlední druhý atd.
    Pozor: převrací se pořadí řetězců, nikoli pořadí binárních číslic uvnitř řetězce.
  • X + Y značí spojení posloupností X a Y za sebe.

Každé sedadlo v parlamentu má svoje číslo, čísla sedadel tvoří souvislou posloupnost začínající jedničkou. Supertajný Kód SK(n) se generuje popsaným způsobem pro větší a větší n, a to tak dlouho, než je délka kódu (tedy počet binárních řetězců v posloupnosti) větší nebo rovna nejvyššímu existujícímu číslu sedadla. Sedadlu s číslem s je přiřazen vždy takový binární řetězec, který se vyskytuje na s-tém místě v posloupnosti SK(n). Tyto tajné kódy se pak rozdají poslancům.

Problém nastavá ve chvíli, kdy poslanec přijde do parlamentu, prohledá svoji aktovku, vyndá papírek s kódem a hledá místo, kde by se posadil. Pro tyto účely předseda parlamentu rozhodl vytvořit program, do kterého poslanec zadá svůj Supertajný Kód a zjistí podle něj číslo svého sedadla. Jak již jistě tušíte, tento program máte za úkol vytvořit.

Specifikace vstupu

První řádek vstupu obsahuje celé kladné číslo N, které udává počet poslanců hledajících své místo. Dále následuje N samostatných zadání. Každé zadání reprezentuje jednoho poslance a skládá se ze dvou řádek. Na prvním z nich je délka kódu k, 1 <= k <= 30, na druhém řádku je pak samotný kód tvořený přesně k znaky. Každý z těchto znaků je buď 0 nebo 1.

Specifikace výstupu

Pro každého poslance musí výstup obsahovat právě jeden řádek a na něm větu "Poslanec P se posadi na sedadlo cislo S." Namísto P doplňte pořadové číslo daného zadání (počínaje jedničkou). Namísto S doplňte vypočítané číslo sedadla, tedy pořadí zadaného binárního řetězce v kódu SK(k).

Příklad vstupu

5
1
0
4
0000
4
1000
4
1111
8
10101010

Příklad výstupu

Poslanec 1 se posadi na sedadlo cislo 1.
Poslanec 2 se posadi na sedadlo cislo 1.
Poslanec 3 se posadi na sedadlo cislo 16.
Poslanec 4 se posadi na sedadlo cislo 11.
Poslanec 5 se posadi na sedadlo cislo 205.

Okrsky

(název programu: okrsky.c, okrsky.p, okrsky.C)

Předpokládejme, ze byl v ČR zaveden většinový volební systém s M okrsky. V každém volebním okrsku s O oprávněnými voliči, který zároveň představuje jedno místo v parlamentu, soutěží mezi sebou kandidáti mnoha stran. Kandidát je zvolen, má-li více hlasů něž libovolný jiný kandidát. Není znám celkový počet stran, ani jestli všechny strany kandidují ve všech volebních okrscích.

Předseda strany PSOS zadal svému týmu za úkol vytvořit program, který mu řekne, jaký minimální počet hlasů zajišťuje straně absolutní vítězství ve volbách, tedy nadpoloviční počet křesel v parlamentu. Všichni oprávnění voliči se zůčastní voleb a dají některému kandidátovi svůj hlas. V každém volebním okrsku kandiduje minimálně jedna další strana. Strana PSOS má své kandidáty ve všech volebních okrscích. Určete minimální počet hlasů, který zajistí straně PSOS vítězství za všech okolností.

Specifikace vstupu

První řádek vstupu obsahuje celé kladné číslo N, 1 <= N <= 100000, které udává počet zadání. Dále následují jednotlivá zadání. Každé zadání je tvořeno dvěma řádky. Na prvním řádku je celé číslo M, 1 <= M <= 10000, které představuje počet volebních okrsků. Na druhém řádku následuje M čísel oddělených mezerami, která představují počty oprávněných voličů v jednotlivých okrscích. Tato čísla jsou celá kladná a ne větší než 100000.

Specifikace výstupu

Pro každé zadání vypište jeden řádek textu, který bude obsahovat větu "H hlasu zajisti strane vitezstvi.", kde H je minimální počet hlasů, který zajišťuje straně PSOS většinu v parlamentu.

Příklad vstupu

3
10
340 260 180 15 1 20 40 90 78 34
2
12 1
6
1 2 3 4 5 6

Příklad výstupu

1003 hlasu zajisti strane vitezstvi.
13 hlasu zajisti strane vitezstvi.
18 hlasu zajisti strane vitezstvi.

Parlament

(název programu: parlament.c, parlament.p, parlament.C)

Protože poslanci tráví v parlamentu většinu času, chtěla by si politická strana PSOS svá místa vybrat předem tak, aby jí co nejvíce vyhovovala. Pro tento účel PSOS stanovila komisi, která má za úkol ohodnotit všechna místa v parlamentu počtem bodů podle jejich atraktivnosti. Body se přidělují podle toho, jak moc jsou pohodlné polštářky na židličkách, podle polohy kamer, které by mohly přistihnout poslance při spánku a podobně. Nebyl to jednoduchý úkol a tak trvalo několik měsíců, než se komisi podařilo ohodnotit všechna místa v parlamentu. Ideální z hlediska pohodlí by bylo obsadit všechna místa od nejpohodlnějšího postupně všemi členy strany. Bohužel to však není možné. Strana má totiž rovněž komisi, která se stará o utajení informací ve straně. Tato komise stanovila, že poslanci musí sedět pohromadě ve tvaru obdélníku. Další problém je v tom, že dosud neproběhly volby a strana tedy neví, kolik získá v parlamentu míst. Protože je potřeba udělat odhad umístění poslanců v parlamentu, shání strana programátora, který by jí napsal program, který pro dané umístění poslanců zjistí atraktivnost takového umístění.

Specifikace vstupu

Na prvním řádku zadání je celé kladné číslo N, které udává počet zadání. Dále následují jednotlivá zadání. Na prvním řádku každého zadání jsou celá kladná čísla R a S, kde R udává počet řad v parlamentu a S udává počet míst v každé řadě (všechny řady mají stejně sedadel), přičemž je známo, že žádný parlament nemá více než 1000 řad a řada nemá více než 1000 sedadel. Následuje R řádků, každý z nich popisuje jednu řadu parlamentu, od první do poslední. Na každém z těchto řádků je právě M čísel oddělených mezerami. Tato čísla udávají ohodnocení jednotlivých sedadel v dané řadě, postupně od prvního. Velikost všech těchto čísel bude volena tak, aby se součet ohodnocení všech míst v parlamentu vešel do standardního typu int popř. integer.

Dále následuje celé kladné číslo D, které udává počet dotazů na takto zadané ohodnocení míst. Následuje D dotazů, každý na samostatném řádku. Každý dotaz je tvořen souřadnicemi R1S1, R2S2 (v tomto pořadí)oddělenými mezerou, 1 <= R1 <= R2 <= R <= 1000, 1 <= S1 <= S2 <= S <= 1000. To znamená, že poslanci sedí na místech ve tvaru obdélníku v řadách R1R2 (včetně) a v každé z těchto řad na místech S1S2 (včetně).

Specifikace výstupu

Pro každý dotaz vypište na výstup jediný řádek a na něm větu "Absolutni hodnota pohodlnosti je X bodu.", kde za X se dosadí hodnota pohodlnosti. Tato hodnota se zjistí jako prostý součet jednotlivých ohodnocení pro všechna místa obsazená stranou PSOS. Na konci každého zadání (včetně posledního) vytiskněte jeden prázdný řádek.

Příklad vstupu

2
10 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
5
1 1 1 1
2 2 2 2
1 1 10 10
9 9 10 10
2 2 9 9
1 1
1
1
1 1 1 1

Příklad výstupu

Absolutni hodnota pohodlnosti je 1 bodu.
Absolutni hodnota pohodlnosti je 2 bodu.
Absolutni hodnota pohodlnosti je 550 bodu.
Absolutni hodnota pohodlnosti je 38 bodu.
Absolutni hodnota pohodlnosti je 352 bodu.

Absolutni hodnota pohodlnosti je 1 bodu.

Ruleta

(název programu: ruleta.c, ruleta.p, ruleta.C)

Z toho, že jste o politické straně PSOS delší dobu neslyšeli, je zřejmé, že se doposud vyhnula veškerým skandálům s neznámými sponzory. Bohužel to bylo na úkor jejího financování, protože jí žádný sponzor peníze neposlal. Blížící se volby jsou finančně velice náročnou záležitostí a jejich výsledek nechtějí členové strany v žádném případě nechat náhodě. Rozhodli se vzít celou situaci pevně do svých rukou. Snaha získat nějaké sponzory však vyzněla do prázdna, protože všichni, kteří byli ochotni přispět, chtěli zůstat v naprosté anonymitě.

Několika členům se nakonec podařilo proniknout do herního průmyslu, do oblasti, ve které se jeden jejich známý v minulosti zabýval konstrukcí elektronických her. Mimo jiné se tento člověk podílel i na konstrukci nové, plně digitální rulety v Monte Carlu. Členové strany PSOS ho rychle přesvědčili, aby se k nim přidal. V rámci povinného kursu stranické pravdomluvnosti ho přiměli, aby jim prozradil, že náhodný generátor rulety v Monte Carlu se řídí rovnicí:

xk+1 = (A . xk) mod 47

kde konstantu rulety A určuje ředitel kasina Karel Monte každé ráno a xk+1 je číslo, které následuje za číslem xk. Členové strany se okamžitě vypravili do Monte Carla získat finance pro svojí stranu. Jejich problém je v tom, že člověk, který ruletu konstruoval, stranický kurs pravdomluvnosti nepřežil. Proto hledají někoho, kdo by napsal program, který jim pro každou posloupnost čísel

xt-n, xt-n+1, ..., xt-1, xt

vyhovující zmíněné rovnici prozradí, kolik je následující číslo xt+1. Číslo A i čísla xi jsou celá a nezáporná, menší než 1000000.

Specifikace vstupu

První řádek vstupu obsahuje celé kladné číslo N, které udává počet zadání. Dále následují jednotlivá zadání. Každé zadání je tvořeno dvěma řádky, první řádek obsahuje celé nezáporné číslo M, na druhém řádku je posloupnost M čísel x1, x2, x3, ..., xM oddělených mezerami.

Specifikace výstupu

Pro každé zadání vypište jednu řádku. Je-li možné zjistit, jaké bude další číslo, vypište větu "Vsad na X.", kde místo X uveďte číslo, které bude v posloupnosti následovat. Není-li to možné zjistit pro nedostatek informací, vypište větu "Dalsi cislo nelze urcit." Pokud posloupnost nevyhovuje výše zmíněné rovnici pro žádné A, vypište větu "Algoritmus byl zmenen."

Příklad vstupu

3
1
5
3
7 33 28
3
25 26 25

Příklad výstupu

Dalsi cislo nelze urcit.
Vsad na 38.
Algoritmus byl zmenen.

Sekretářka

(název programu: sekretarka.c, sekretarka.p, sekretarka.C)

Předpokladem úspěchu každé politické strany je dobře zpracovaný volební program. To si nedávno uvědomilo i předsednictvo PSOS, a tak úkolem sestavení nového programu pověřilo nejvyšší sekretářku Mahulenu. Mahulena si ale svoji práci chtěla zjednodušit, a tak přesvědčila svým půvabem a osobním kouzlem sekretáře nejmenované konkurenční strany Raduze, aby jí pomohl. Ale protože Raduz uměl celý text volebního programu své strany nazpaměť, neubránil se a části textu, který psal pro Mahulenu, opsal z programu své strany. Když se poté Raduz a Mahulena sešli a objevili nápadnou podobnost obou programů, chtěli zjistit, jaký nejdelší společný úsek textu oba volební programy obsahují.

Specifikace vstupu

První řádek vstupu obsahuje celé kladné číslo N, 1 <= N <= 100000, které udává počet zadání. Každé zadání se skládá ze dvou řádek textu o délce L znaků, 1 <= L <= 10000. Znaky "konec řádku" nejsou součástí zadání.

Specifikace výstupu

Pro každé zadání musí výstup obsahovat text: "Nejdelsi spolecny retezec ma delku X.", kde X je délka nejdelšího společného souvislého úseku obou textů.

Příklad vstupu

2
Tady nejsou zadni mimozemstani.
Lide tady take nejsou.
Ja do lesa nepojedu.
V sobotu pojedeme na vylet.

Příklad výstupu

Nejdelsi spolecny retezec ma delku 7.
Nejdelsi spolecny retezec ma delku 5.