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 1 až n (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
X, Y, Z oddělených
mezerami, 1 <= X,Y,Z <= 100. Všechny zaplavené prostory
jeskyně jsou uvnitř kvádru o stránách
X, Y, Z 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
R1, S1,
R2, S2 (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
R1 až R2 (včetně) a
v každé z těchto řad na místech S1 až
S2 (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.
|