Zadání úloh ústředního kola (1. soutěžní den) 53. ročníku
Všeobecné pokyny
Na řešení úloh máte 4,5 hodiny čistého času.
Řešení každého příkladu musí obsahovat:
- Popis řešení,
to znamená slovní popis použitého algoritmu, argumenty
zdůvodňující jeho správnost (případně důkaz správnosti
algoritmu), diskusi o efektivitě vašeho řešení (časová a paměťová
složitost). Slovní popis řešení musí být jasný a srozumitelný
i bez nahlédnutí do samotného zápisu algoritmu (do programu).
- Program,
v úlohách P-III-1 a P-III-2 je třeba
uvést dostatečně podrobný zápis algoritmu, nejlépe ve tvaru
zdrojového textu nejdůležitějších částí programu v jazyce Pascal
nebo C. Ze zápisu můžete vynechat jednoduché operace jako vstupy,
výstupy, implementaci jednoduchých matematických vztahů apod.
V úloze P-III-3 uveďte příslušné programy pro registrové počítače.
Hodnotí se nejen správnost programu, ale také kvalita popisu
řešení a efektivita zvoleného algoritmu.
P-III-1 Agenti
Jistá nejmenovaná tajná společnost má N agentů. Z důvodu utajení
může každý agent vydávat rozkazy jen několika dalším agentům. Agent,
který dostane rozkaz, pošle tento rozkaz všem agentům, jimž může
vydávat rozkazy. Šéfem společnosti je takový agent, který když vydá rozkaz, tak
ho časem dostanou všichni agenti. (Společnost může mít i více šéfů, případně nemusí mít žádného šéfa.)
Soutěžní úloha
Na vstupu je dán počet agentů N. Agenti jsou označeni čísly od 7 (přesněji 007) do
N+6. Pro každého agenta je také dán seznam agentů, kterým může
vydat rozkaz. Navrhněte efektivní algoritmus, který určí šéfa tajné
společnosti (pokud jich existuje více, stačí nalézt jednoho libovolného z nich)
nebo zjistí, že tajná společnost žádného šéfa nemá.
Příklad 1
Vstup:
N=3
Agent 7 rozkazuje agentovi 8.
Agent 8 rozkazuje agentovi 9.
Agent 9 rozkazuje agentovi 7.
Výstup:
Šéfem je agent 7.
Příklad 2
Vstup:
N=4
Agent 7 nerozkazuje nikomu.
Agent 8 nerozkazuje nikomu.
Agent 9 rozkazuje agentům 7 a 8.
Agent 10 rozkazuje agentům 7 a 8.
Výstup:
Žádný agent není šéfem.
P-III-2 Teploty
Meteorologická stanice měří každou minutu teplotu vzduchu. Meteorologové
by potřebovali program, který by jim v každém okamžiku sděloval, jaká nejnižší
teplota byla naměřena během posledních K minut. Vaším úkolem bude napsat
tento program.
Na vstupu je dáno číslo K, následuje posloupnost naměřených teplot ukončená
hodnotou -1000. Váš program musí po přečtení každé teploty ihned vypsat
nejnižší z posledních K načtených teplot (resp. nejnižší
ze všech načtených teplot, jestliže jich dosud bylo méně než K).
Příklad
Vstup:
K=3
Teploty:
9.0
4.7
5.3
2.1
9.0
9.8
17.0
9.5
-1000
Výstup:
9.0
4.7
4.7
2.1
2.1
2.1
9.0
9.5
P-III-3 Registrový počítač
V tomto kole se budeme zabývat tzv.
jednosměrnými registrovými
počítači - stejnými jako v domácím kole. Jejich formální definici najdete ve studijním textu,
který následuje za zadáním soutěžní úlohy a je zcela shodný se studijním textem z domácího kola.
Soutěžní úloha
- Nechť R je řetězec tvořený písmeny a, b, c, A, B, C.
Označme m(R) řetězec tvořený malými písmeny obsaženými v R (ve stejném pořadí, v jakém se vyskytují
v R). Analogicky označme v(R) řetězec tvořený velkými písmeny v R.
Řetězec upcase(R) dostaneme z R tak, že nahradíme všechna malá písmena
odpovídajícími velkými písmeny.
Např. jestliže R=aaAcB, potom m(R)=aac, v(R)=AB a upcase(R)=AAACB.
Napište program pro jednosměrný registrový počítač, který bude řešit následující úlohu:
Na vstupu dostane řetězec R tvořený písmeny a, b, c, A, B, C.
Počítač ho má označit za správný právě tehdy, když upcase(m(R))=v(R).
(Vyjádřeno slovně: když velká písmena obsažená v R tvoří "stejné" slovo jako malá.)
Například vstupní řetězce aA, Aa a abAcBaCABb jsou tedy správné, zatímco řetězce aa, BcbC a acACa jsou špatné.
Váš program může použit libovolný konečný počet registrů, hodnotí se jen jeho správnost.
Pokud si myslíte, že takový program neexistuje, dokažte to.
- Dokažte, že pro libovolnou úlohu platí: Jestliže umíme sestrojit program pro registrový počítač,
který řeší danou úlohu pomocí tří registrů, potom dokážeme sestrojit také program, který tuto úlohu
řeší pomocí dvou registrů.
Jinými slovy: Ukažte postup, kterým lze libovolný existující program
používající tři registry přepsat na ekvivalentní program, jenž potřebuje pouze dva registry.
Nezapomeňte zdůvodnit správnost svého postupu.
Studijní text
Registr je něco podobného jako proměnná. V registru může být
uloženo
libovolně velké nezáporné celé číslo. Na rozdíl od
proměnných, které mezi sebou můžeme sčítat, odčítat a násobit,
s registrem lze provádět jen tři jednoduché operace: zvětšit jeho
obsah o 1, zmenšit jeho obsah o 1 (pokud se pokusíme zmenšit obsah
registru obsahujícího hodnotu 0, zůstane v něm 0) a otestovat registr,
zda je v něm 0. Na začátku výpočtu jsou ve všech registrech
nuly.
Registrový počítač může používat neomezený počet registrů označených
R0, R1, R2, atd.
Vedle registrů má k dispozici ještě konečně
velkou pomocnou paměť.
Program pro registrový počítač budeme zapisovat v jazyce velmi podobném
programovacímu jazyku Pascal. Programovací jazyk registrového počítače bude
oproti Pascalu rozšířen například o příkazy pro práci s registry, naopak
některé příkazy z Pascalu v něm budou zakázány.
Registrový počítač bude řešit úlohy následujícího typu: počítač dostane na
vstupu zadáno slovo (řetězec písmen) a po nějakém čase odpoví, zda je toto
slovo správné nebo špatné. Aby nám mohl odpovědět, zavedeme do
programovacího jazyka speciální příkazy Accept a Reject. Jakmile se během
výpočtu vykoná příkaz Accept, vstupní slovo je správné a výpočet končí.
Jestliže se provede příkaz Reject, slovo je špatné a výpočet končí. Pokud se
výpočet zacyklí nebo pokud skončí, aniž by se provedl příkaz Accept nebo
Reject, zadané vstupní slovo je rovněž špatné.
Příkaz "přičti 1 k obsahu registru R" budeme značit Inc(R), "odečti 1 od
obsahu registru R" budeme značit Dec(R).
Výraz Zero(R) je pravdivý, jestliže je v registru R nula,
v opačném případě je nepravdivý. Na začátku
výpočtu jsou ve všech registrech nuly.
V každém programu můžeme použít jen konečně mnoho registrů. Kromě nich můžeme
použít už jen konstantní počet pomocných proměnných typu
byte (taková proměnná
obsahuje jedno celé číslo z rozmezí od 0 do 255 a
nemůžeme tedy používat pole!) a jednu speciální proměnnou vstup typu
char.
Obsah proměnné vstup lze měnit pouze provedením příkazu Read(vstup).
Jestliže počítač ještě nedočetl vstupní slovo, příkaz Read(vstup) z něj
přečte jedno další písmeno a uloží ho do proměnné vstup. Pokud počítač již
vstupní slovo dočetl, příkaz Read(vstup) uloží do proměnné vstup speciální
znak $.
Jelikož registrový počítač má kromě registrů jen konečně mnoho paměti, nemůže
si dovolit používat rekurzi (neměl by si kde pamatovat návratové adresy). My
pro jistotu úplně zakážeme definovat a používat v programu procedury a funkce.
Zakázáno je i volání všech standardních procedur a funkcí jazyka Pascal.
V aritmetických výrazech lze používat pouze proměnné (tedy ne registry!),
celočíselné konstanty, celočíselné operátory +, -, *, div,
mod a závorky. V podmínkách se mohou používat
výrazy Zero(Ri), běžné
relační operátory (<, <=, ...), logické spojky a závorky.
Z klíčových slov jazyka Pascal jsou tedy v programovacím jazyku registrového počítače povolena pouze následující:
var,
begin,
end,
if,
then,
else,
case,
of,
while,
do,
repeat,
until,
for,
to,
downto,
div,
mod,
and,
or,
not a
xor.
Příklad 1
Napište program pro registrový počítač, který bude řešit následující úlohu. Na
vstupu je zadán řetězec písmen a, b, c. Nechť A označuje počet těch
písmen a ve vstupním řetězci, za kterými už není žádné c. Podobně nechť B
je počet b, za nimiž není žádné c. Počítač má vstupní řetězec označit za
správný právě tehdy, když A=B.
Řešení
V registru R
1 si budeme pamatovat aktuální hodnotu A,
v registru R
2 hodnotu B.
Pokaždé, když přečteme ze vstupu písmeno c, oba registry vynulujeme.
Na konci výpočtu jednoduše porovnáme hodnoty uložené v registrech. Rozmyslete
si, že by stačilo použít jen jeden registr (v němž bychom měli
hodnotu |A-B|).
var vstup:char;
begin
Read(vstup);
while (vstup<>'$') do begin
if (vstup='a') then Inc(R1);
if (vstup='b') then Inc(R2);
if (vstup='c') then begin
while not Zero(R1) do Dec(R1);
while not Zero(R2) do Dec(R2);
end;
Read(vstup);
end;
while not Zero(R1) do begin
Dec(R1);
if (Zero(R2)) then Reject;
Dec(R2);
end;
if Zero(R2) then Accept;
end.
Příklad 2
Napište program pro registrový počítač, který bude řešit následující úlohu. Na
vstupu bude zadán řetězec písmen a. Počítač ho označí za správný právě tehdy,
když je jeho délka mocninou tří.
Řešení
Přečteme vstupní slovo, přičemž si do R
1 uložíme jeho délku.
Potřebujeme
zjistit, zda je to mocnina tří. Uloženou hodnotu proto budeme dělit třemi,
dokud to půjde. Jestliže nakonec dostaneme podíl 0 a zbytek 1, původní číslo
bylo mocninou tří, jinak nebylo.
var vstup:char;
zbytek:byte;
begin
Read(vstup);
while (vstup<>'$') do begin Inc(R1); Read(vstup); end;
if Zero(R1) then Reject;
while true do begin
zbytek:=0;
while not Zero(R1) do begin
Dec(R1);
zbytek:=(zbytek+1) mod 3;
if (zbytek=0) then Inc(R2);
end;
if (Zero(R2) and (zbytek=1)) then Accept;
if (zbytek<>0) then Reject;
while not Zero(R2) do begin Dec(R2); Inc(R1); end;
end;
end.