Matematická olympiáda – kategorie P

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:

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

  1. 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.

  2. 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 R1 si budeme pamatovat aktuální hodnotu A, v registru R2 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 R1 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.