Matematická olympiáda – kategorie P

Zadání úloh oblastního kola 49. ročníku

Druhé kolo 49. ročníku MO kategorie P se koná v úterý 11. 2. 2000 v dopoledních hodinách. Na řešení úloh máte 4 hodiny čistého času. Řešení každého příkladu musí obsahovat (není-li v zadání některé úlohy uvedeno jinak):

• 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-II-1, P-II-2 a P-II-3 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 jazyku 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-II-4 uveďte místo programu schéma navrženého registrového stroje.

Hodnotí se nejen správnost programu, ale také kvalita popisu řešení a efektivita zvoleného algoritmu.

P-II-1 Síť

Ve výpočetním středisku mají N počítačů očíslovaných od 1 do N. Počítače jsou navzájem propojeny jednosměrnými spoji. Jestliže je počítač i připojen k počítači j, znamená to, že počítač i může posílat zprávy počítači j (ale ne naopak). Jestliže je počítač i připojen k počítači j, může, ale nemusí být připojen také počítač j k počítači i. (Žádný počítač není připojen sám k sobě.)

Do výpočetního střediska nyní koupili nový centrální počítač. Je třeba zajistit, aby tento nový počítač mohl poslat zprávu všem ostatním počítačům. Musíme ho proto připojit k některým dalším počítačům tak, aby se z něj dala poslat zpráva libovolnému počítači p buď přímo (tj. centrální počítač je připojen k počítači p), nebo přes několik jiných počítačů (tj. existují počítače a₁, a₂, ..., a_k takové, že centrální počítač je připojen k počítači a₁, pro i=1,2,... k-1 je počítač a_i připojen k počítači a_i+1 a počítač a_k je připojen k počítači p). Kvůli úspoře kabelů je přitom nutné minimalizovat počet počítačů, ke kterým bude nový centrální počítač připojen.

Úloha

Je dán počet počítačů N. Pro každý počítač i (1 <= i <= N) je dán počet počítačů d_i, k nimž je daný počítač připojen, a dále je dán seznam těchto počítačů a_i1, a_i2, ... a_id(i). Napište program, který vypíše seznam počítačů, k nimž je třeba připojit nový centrální počítač tak, aby jejich počet byl minimální. Pokud je možné centrální počítač připojit více způsoby, vypište libovolný jeden z nich.

Příklad

Vstup:
N = 7
d₁ = 1, připojení: 2
d₂ = 2, připojení: 1 5
d₃ = 1, připojení: 6
d₄ = 2, připojení: 3 6
d₅ = 1, připojení: 3
d₆ = 1, připojení: 5
d₇ = 0, připojení: -
Výstup:
2,4,7
(Jiné možné řešení je 1,4,7.)

P-II-2 Posloupnost

Nechť A = (a₁, a₂, ..., a_M) je posloupnost celých čísel. Posloupnost A' nazveme vybranou podposloupností této posloupnosti, jestliže vznikne z posloupnosti A vynecháním některých jejích členů, přičemž pořadí ostatních prvků zachováme. Společná vybraná podposloupnost posloupností A, B je každá taková posloupnost C, která je vybranou podposloupností obou posloupností A i B.

Příklad

Nechť A = (1,11,2,1,4,99), B = (9,4,1,2,7,1,99). Posloupnost (1,2,1,99) je společnou vybranou podposloupností posloupností A, B. Posloupnost (1,2,4) je vybranou podposloupností posloupnosti A, ale není vybranou podposloupností posloupnosti B, takže není ani společnou vybranou podposloupností A a B.

Soutěžní úloha

Máme dány dvě posloupnosti celých čísel A = (a₁,a₂, ..., a_M) a B = (b₁,b₂, ..., b_N) s délkami M, resp. N. Tyto posloupnosti jsou uloženy v polích a[1..M], resp. b[1..N], jejichž obsah není dovoleno měnit. Uvažujme takovou společnou vybranou podposloupnost posloupností A a B, ve které součet všech jejích členů je největší možný. Napište program, který vypíše součet členů takovéto posloupnosti.

Poznámka: Existuje algoritmus, který tuto úlohu řeší v čase úměrném M x N a paměti, jejíž velikost je úměrná menšímu z čísel M, N.

Příklad

Vstup:
M=6, N=7
A=(1,11,2,1,4,99)
B=(9,4,1,2,7,1,99)
Výstup:
103
(Vybrané podposloupnosti se součtem 103 existují dvě: 4,99 a 1,2,1,99.)

P-II-3 Volby

V jisté zemi právě skončily volby. Každý volič v nich hlasoval pro jednoho z navržených kandidátů. Vítězem voleb se stane kandidát, pro kterého hlasovala nadpoloviční většina voličů. Máte k dispozici výsledky hlasovaní jednotlivých voličů a máte co nejrychleji zjistit, který kandidát vyhrál volby.

Soutěžní úloha

Voleb se zúčastnilo N voličů očíslovaných od 1 do N a M kandidátů očíslovaných od 1 do M (někteří kandidáti však nemuseli získat ani jeden hlas). Výsledky hlasování jsou uloženy v poli a, přičemž platí, že volič i (1 <= i <= N) hlasoval pro kandidáta číslo a_i. Obsah tohoto pole nesmíte měnit.

Napište program, který zjistí, zda existuje kandidát, pro kterého hlasovalo více než N/2 voličů. Jestliže takový kandidát existuje, program vypíše jeho číslo, pokud ne, program vypíše, že takový kandidát neexistuje.

Poznámka: Čísla M a N mohou být velmi velká. Snažte se proto, aby váš program pracoval co nejefektivněji a aby používal co nejméně paměti.

Příklad

Vstup:
N=9
A={2,3,2,2,3,50001,3,2,2}
Výstup: Vyhrál kandidát 2.

Vstup:
N=10
A={2,2,1,4,3,2,1,2,100,2}
Výstup: Nevyhrál žádný kandidát.

P-II-4 Minského registrové stroje

Definice

(Oproti domácímu kolu je popis registrového stroje rozšířen o nový druh příkazu - výpočet hodnoty funkce.)

Minského registrový stroj je jednoduché výpočetní zařízení. K dispozici má několik registrů označených R₀, R₁, R₂,..., přičemž v každém registru může být uloženo jedno libovolně velké nezáporné celé číslo.

Minského registrový stroj může mít jeden nebo více vstupů, jejichž hodnoty jsou na začátku výpočtu uloženy v registrech R₁,...,R_k, kde k je počet těchto vstupů. Ostatní registry jsou na začátku výpočtu inicializovány na hodnotu nula. Po skončení výpočtu Minského registrového stroje je výsledkem hodnota uložená v registru R₀.

Každý Minského registrový stroj je řízen pevně daným programem. V programu se mohou vyskytovat tyto příkazy:

• Zvýšení hodnoty v daném registru o 1.
• Snížení hodnoty v daném registru o 1 (pokud je v registru nula, hodnota se nezmění).
• Test na nulu zjistí, zda je v daném registru nula.
• Výpočet hodnoty funkce FTento příkaz vezme obsah určeného vstupního registru (označme tuto hodnotu registru jako x), vypočítá hodnotu F(x) a uloží ji do určeného výstupního registru. Obsah vstupního registru po provedení tohoto příkazu není definován (může v něm být libovolné nezáporné číslo).

Registr je určen svým číslem. Číslo registru je v příkazu vždy pevně zadáno, není tedy možné k určení registru použít obsah jiného registru.

Programy budeme zakreslovat do schémat, přičemž zvýšení hodnoty registru R_i budeme značit obdélníkem s nápisem R_i++, snížení hodnoty registru R_i budeme značit obdélníkem s nápisem R_i--, test na nulu v registru R_i značíme oválem s nápisem R_i?. Příkaz na výpočet funkce F se vstupním registrem R_i a výstupním registrem R_j značíme obdélníkem s nápisem R_j <- F(R_i) (vstupní a výstupní registr musí být navzájem různé).

Začátek programu označujeme písmenem Z v kroužku a konec programu písmenem K v kroužku (program může mít i více konců, ale jen jeden začátek). Jednotlivé příkazy jsou pospojovány šipkami, které určují tok řízení programu. Z obdélníka vychází vždy jediná šipka. Z oválu vycházejí dvě šipky, přičemž jedna z nich je označena nulou (po ní pokračuje výpočet tehdy, když byla v testovaném registru nula, v opačném případě výpočet sleduje druhou šipku). Jestliže v programu za sebou následuje několik příkazů zvýšení nebo snížení, můžeme je napsat pod sebe do jednoho obdélníku.

Příklad

Nechť F(x) je předem daná, ale neznámá funkce. Sestrojte registrový stroj, který dostane na vstupu jedno číslo n (uložené v registru R₁) a který spočítá součet F(0)+F(1)+...+F(n-1) (uloží ho do registru R₀).

Řešení

Stroj řešící zadanou úlohu vidíme na obrázku. Tento stroj pracuje v cyklu. Při každém průchodu cyklem sníží hodnotu uloženou v registru R₁ o jedničku, vypočítá hodnotu funkce F(R₁) a přičte ji k registru R₀. Budeme potřebovat několik pomocných registrů. Registr R₃ bude sloužit jako vstupní registr pro výpočet funkce F. Do tohoto registru zkopírujeme obsah registru R₁ tak, že nejprve "přesypeme" obsah registru R₁ do registrů R₃ a R₄ a potom zpět obsah R₄ do R₁. Nyní můžeme použít příkaz na výpočet funkce F. Výsledek výpočtu funkce se zapíše do registru R₂. Na dokončení jednoho průchodu cyklem nyní stačí "přisypat" obsah R₂ do registru R₀ a vynulovat registr R₃.

Soutěžní úlohy

1. Nechť F(x) je nějaká předem daná, ale neznámá rostoucí funkce. (Funkce je rostoucí, jestliže pro všechna x platí F(x+1) > F(x).) Sestrojte registrový stroj s jedním vstupem y, který bude počítat funkci G(y) inverzní k funkci F. Přesněji řečeno, výsledek výpočtu registrového stroje G(y) = x, kde x je nejmenší takové nezáporné celé číslo, pro které platí F(x) >= y.

   Příklad

   Předpokládejme, že F(x) = x²+6. Potom pro vstupní hodnotu y=5 by měl stroj vypočítat výsledek 0 (protože F(0) >= 5 a 0 je nejmenší nezáporné celé číslo). Pro vstup y=10 je správným výstupem 2, pro vstup y=11 je správná výstupní hodnota 3.

2. Sestrojte Minského registrový stroj s jedním vstupem n, který zjistí, zda je zápis čísla n ve dvojkové soustavě palindromem. Palindrom je posloupnost cifer, která je stejná, když se čte zepředu i zezadu (není povoleno dopisovat nuly na začátek zápisu čísla). Stroj bude na konci výpočtu obsahovat v registru R₀ jedničku v případě, že dvojkový zápis čísla n je palindrom, nebo nulu v případě, že palindromem není.

   Příklad

   Zápisy čísel 0₁₀ = 0₂ nebo 21₁₀ = 10101₂ ve dvojkové soustavě jsou palindromy, zápisy čísel 10₁₀ = 1010₂ a 11₁₀ = 1011₂ palindromy nejsou.