Matematická olympiáda – kategorie P

Řešení úloh ústředního kola 43. ročníku

P-III-1

Daná posloupnost N čísel je tvořena čísly a1,a2,...,aN. Pro každé číslo ai můžeme určit hodnotu ei udávající, o kolik více bylo kladných čísel než záporných v počátečním úseku posloupnosti a1a2...ai. Pokud bylo v úseku a1a2...ai více záporných čísel, bude mít ei zápornou hodnotu. Pro každé pořadové číslo prvku i od 1 do N bude jistě platit nerovnost -i<=ei<=i.

Každý vybalancovaný úsek posloupnosti apap+1...aq-1aq je charakterizován tím, že jeho krajní prvky ap-1, aq mají stejnou tuto e-hodnotu, tj. ep-1=eq. Pokud tedy určíme všechny hodnoty ei pro i od 1 do N, stačí mezi nimi nalézt dvojici stejných hodnot co nejvíce od sebe vzdálených. Jejich vzdálenost od sebe v posloupnosti pak přímo udává délku maximálního vybalancovaného úseku. Jestliže neexistuje žádná dvojice stejných hodnot ep-1=eq, jsou všechna čísla v posloupnosti kladná nebo všechna záporná a daná posloupnost tedy neobsahuje žádný vybalancovaný úsek.

Výpočet hodnot ei pro všechna i od 1 do N je velmi snadný. Stačí jednou projít celou posloupností a za každé kladné, resp. záporné číslo přičíst k průběžně počítané hodnotě +1, resp. -1. Formálně zapsáno, položíme e0=0 a potom:

Bylo by možné uložit si všechny hodnoty ei do pole a v něm pak vyhledávat dvojice stejných hodnot. Takový postup je ale zbytečně pomalý. Lepší je ukládat si do pomocného pole F pro každou dosaženou e-hodnotu M nejmenší takové p, že ep=M. Vzhledem k podmínce -i<=ei<=i musí být toto pole indexováno od -N do N. Využívat se z něj bude přitom pouze jistý souvislý úsek s indexy od X do Y. Během čtení a zpracovávání prvků posloupnosti se velikost tohoto úseku může zvětšovat.

Na začátku výpočtu položíme X=0, Y=0 a F[0]=0. Postupně budeme číst čísla tvořící danou posloupnost a zpracovávat je. Po přečtení čísla ai nejprve spočítáme hodnotu ei podle výše uvedeného předpisu (na základě zaznamenané předchozí hodnoty ei-1). Jestliže ei<X, musí být nutně ei=X-1. Zmenšíme tedy X o 1 a zaznamenáme výskyt nové e-hodnoty F[X]=i. Podobně pro ei>Y zvětšíme Y o 1 a uložíme hodnotu F[Y]=i. Je-li ei z intervalu , stejná e-hodnota byla již nalezena někdy dříve, a sice poprvé při zpracování prvku s pořadím F[ei]. To znamená, že nejdelší vybalancovaný úsek končící prvkem ai má délku i-F[ei]. Nyní zbývá jen porovnat tuto délku s průběžně ukládaným maximem z délek nalezených vybalancovaných úseků.

Popsaný algoritmus je jistě konečný, jediný jeho cyklus se provádí pouze jednou pro každé číslo dané posloupnosti. Má tedy lineární časovou složitost. Správnost algoritmu vyplývá ze skutečnosti, že systematicky prozkoumáme maximální vybalancované úseky končící každým z prvků posloupnosti a z jejich délek vybereme maximum.

program Vybalancovany_Usek; const MaxN=1000; var N:integer; {počet čísel v posloupnosti} A:integer; {právě zpracovávané číslo} E:integer; {e-hodnota zpracovávaného čísla} I:integer; {pořadí zpracovávaného čísla} X,Y:integer; {meze rozsahu nalezených e-hodnot} F:array[-MaxN..MaxN] of integer; {indexy prvních výskytů jednotlivých e-hodnot} Max:integer; {délka max. vybalancovaného úseku} begin X:=0; Y:=0; F[0]:=0; E:=0; Max:=0; for I:=1 to N do begin read(A); {další zpracovávané číslo} if A>0 then E:=E+1 {spočítání jeho e-hodnoty} else if A<0 then E:=E-1; if E<X then {nová nejmenší e-hodnota} begin X:=X-1; F[X]:=I end else if E>Y then {nová největší e-hodnota} begin Y:=Y+1; F[Y]:=I end else {další výskyt stejné e-hodnoty} if I-F[E]>Max then Max:=I-F[E] end; if Max=0 then writeln('Vybalancovany usek neexistuje!') else writeln('Delka maximalniho vybalancovaneho useku: ',Max) end.

P-III-2

Úloha P-III-2 je jednou z klasických úloh teorie grafů. Silniční síť představuje souvislý neorientovaný graf, v němž vrcholy grafu odpovídají městům a hrany grafu silnicím. Nepostradatelné silnice, tak jak jsou definovány v zadání úlohy, odpovídají v teorii grafů zvláštním hranám zvaným mosty. Úkolem tedy je nalézt v daném grafu všechny mosty.

Algoritmus řešení je založen na procházení zadaným grafem do hloubky. Při procházení bude každý vrchol grafu navštíven právě jednou. Způsob procházení lze znázornit stromem. Kořenem stromu procházení je vrchol, z něhož bylo procházení zahájeno. Za kořen můžeme zvolit libovolný vrchol grafu. Bezprostředními následníky některého vrcholu V jsou všechny ty vrcholy, do nichž prohledávání z vrcholu V bezprostředně pokračovalo. Protože zadaný graf je souvislý, budou ve stromu procházení obsaženy všechny vrcholy původního grafu (města). Ze všech hran (silnic) budou ve stromě procházení obsaženy jen ty, které nás v průběhu procházení dovedly do nového, doposud nenavštíveného vrcholu.

Představme si, že do stromu procházení dokreslíme zelenou barvou všechny zbývající hrany grafu. To jsou tedy takové, kterými průchod do hloubky nepokračoval. Jinak řečeno, v průběhu procházení tyto silnice vedly z právě procházeného města do jiného, již dříve navštíveného města. Doplněný strom tedy bude izomorfní s původním grafem.

Nyní vyslovíme jedno pomocné tvrzení: Oba koncové vrcholy každé zelené hrany leží na téže větvi stromu procházení. Tvrzení snadno dokážeme sporem. Předpokládejme, že by některá zelená silnice spojovala dvě města A a B, která neleží na jedné větvi stromu procházení. Označme je tak, že během průchodu bylo A poprvé navštíveno dříve než B. Město B jistě neleží v podstromu procházení s kořenem A (jinak by A a B ležela na téže větvi). Pro postup procházení to znamená, že nejprve bylo (případně několikrát) navštíveno město A a teprve potom (případně několikrát) navštíveno město B. Všimněme si okamžiku během procházení, kdy jsme město A navštívili naposledy. To bylo v situaci, kdy jsme se z něho vraceli zpět (kdybychom šli vpřed, museli bychom do A přijít ještě na zpáteční cestě). V tomto okamžiku jsme se ale nezachovali správně podle algoritmu procházení grafem do hloubky: vraceli jsme se zpět, a přitom jsme ještě měli projít silnicí AB, protože ta vedla do tehdy ještě nenavštíveného města B.

K tomu, aby hrana byla mostem, je nutné a stačí, aby se jejím odstraněním oddělil podstrom ve stromu procházení, který nebude dostupný ani po některé zelené hraně. Podle předchozího tvrzení by takové spojení zelenou hranou muselo vést do vyšší vrstvy ve stromě procházení.

Na základě provedených úvah již lze zformulovat algoritmus. Zadaný graf budeme procházet do hloubky, začít můžeme libovolným vrcholem (např. vrcholem číslo 1). Během procházení si budeme u každého vrcholu M pamatovat jeho hloubku ve stromě procházení HM. Kořen stromu procházení bude mít hloubku 0. Postupně během průchodu budeme pro každý procházený vrchol M určovat číslo ZM definované takto: ZM je minimum z HM a z hloubek koncových měst všech zelených silnic, které vycházejí z vrcholů v podstromu s kořenem M. ZM je tedy číslo nejvyšší hladiny ve stromě procházení, do které vede přímé spojení zelenou silnicí z nějakého města v podstromu s kořenem M. Přitom si všímáme jen hladin nad vrcholem M. Nastane-li pro některý vrchol M nerovnost ZM < HM, existuje zelená silnice, která spojuje podstrom s kořenem ve vrcholu M se zbytkem grafu. Je-li ZM = HM, je silnice, po níž jsme do M během procházení přišli, mostem.

Zbývá ukázat, jak budeme počítat hodnoty HM a ZM pro vrchol M. Hodnotu HM určíme snadno při prvním vstupu do vrcholu M během procházení grafem - je o 1 větší než odpovídající hodnota HX vrcholu X, z něhož do M přicházíme. Stanovení hodnoty ZM je o něco obtížnější. Hodnota ZM je rovna minimu z hodnoty HM a z hodnot Zi všech vrcholů ležících v podstromu s kořenem ve vrcholu M. Při prvním vstupu do vrcholu M můžeme tudíž inicializovat hodnotu ZM již známou hodnotou HM a pak ji během procházení podstromu vrcholu M budeme případně zmenšovat, bude-li to možné. Při každém dalším příchodu do vrcholu M (tj. při návratu z nějakého následníka vrcholu M) lze hodnotu ZM snížit na Z-hodnotu tohoto následníka. K dalšímu snížení ZM mohou přispět hrany, které vedou z vrcholu M do již navštívených uzlů a po nichž se tudíž při průchodu nepostupuje. Hodnotu ZM můžeme snížit na H-hodnotu koncových vrcholů těchto zelených hran. Definitivní hodnotu ZM získáme až při posledním opuštění vrcholu M.

Složitost celého algoritmu je dána složitostí průchodu grafem do hloubky. Ostatní výpočty spojené s určováním hodnot HM a ZM mají konstantní časové nároky. Časová složitost programu pro průchod grafem do hloubky závisí na vhodné volbě vnitřní reprezentace grafu. Při vhodně zvolené reprezentaci (viz uvedená programová ukázka) je přímo úměrná počtu hran v grafu, tj. je řádu n2, kde n je počet vrcholů grafu.

program Mosty (input,output); { Format ocekavanych vstupnich dat - zadani grafu: - sousedi kazdeho vrcholu vzdy na jednom radku ve tvaru <cislo-vrcholu> <cislo-souseda1> <cislo-souseda2> ... - vrcholy musi byt ocislovany od jedne po jedne a v tomto poradi musi byt take radky na vstupu zadany - kazda hrana se tedy uvadi dvakrat (na radcich pro jeden a pro druhy jeji koncovy vrchol) - program pro jednoduchost netestuje spravnost zadanych vstupnich dat (nebylo by tezke testy doplnit) } const MaxPocetMest = 40; MaxPocetSilnic = 200; type Mesto = 1..MaxPocetMest+1; { fiktivni mesto na konci } Silnice = 1..MaxPocetSilnic; var GMesto : array [Mesto] of record Spoje : Silnice; Hloubka : integer; Projito : Boolean; end; GSilnice : array [Silnice] of Mesto; { pole GMesto a GSilnice predstavuji vnitrni ulozeni grafu - ke kazdemu vrcholu je v poli GSilnice ulozen seznam jeho sousedu, polozka Spoje v GMesto urcuje, kde presne jsou ulozeni sousedi kazdeho konkretniho vrcholu - viz uvodni komentar o tvaru vstupnich dat a procedura NactiGraf } PocetMest : 0..MaxPocetMest; PocetSilnic : 0..MaxPocetSilnic; F:integer; { pomocna promenna - je potrebna pro spravne volani procedury Pruchod v hlavnim programu } procedure NactiGraf; { nacteni vstupnich dat - zadani zkoumaneho grafu } var dummy:integer; begin PocetMest:=0; PocetSilnic:=1; repeat PocetMest:=PocetMest+1; read(dummy); { cislo mesta - nevyuziva se } GMesto[PocetMest].Spoje:=PocetSilnic; while not eoln do begin read(GSilnice[PocetSilnic]); PocetSilnic:=PocetSilnic+1; end; readln; until eof; GMesto[PocetMest+1].Spoje:=PocetSilnic; end; function min(X,Y:integer):integer; { pomocna procedura - minimum ze dvou celych cisel } begin if X<Y then min:=X else min:=Y; end; procedure PisMost(odkud,kam : Mesto); { vypise, ze z mesta "odkud" do mesta "kam" vede most } begin writeln('Most z ',odkud,' do ',kam,'.'); end; procedure PredPruchodem; { oznaci vsechna mesta za dosud neprojita - nutne! } var i:Mesto; begin for i:=1 to PocetMest do GMesto[i].Projito := false; end; procedure Pruchod(Start: Mesto; hl:integer; var Z: integer); { Projde odpovidajici cast grafu do hloubky. Zacina ve meste Start, jeho hloubka je hl, spocita pro nej hodnotu Z (viz text). } var Nasl : Mesto; S : Silnice; pomZ : integer; begin GMesto[Start].Projito := true; { vrchol navstiven } GMesto[Start].Hloubka := hl; { ma hloubku hl } Z := hl; { prozatimni hodnota Z } for S:=GMesto[Start].Spoje to GMesto[Start+1].Spoje-1 do begin Nasl := GSilnice[S]; { mesto dostupne po silnici S } if GMesto[Nasl].Projito then begin { nepocitat silnici, po niz jsme prisli! } if GMesto[Nasl].Hloubka+1 <> hl then { zelena silnice, bud nahoru, nebo dolu } Z := min(Z,GMesto[Nasl].Hloubka) { pokud vede zelena silnice nahoru, snizime hodnotu Z v nasem uzlu } end else begin Pruchod(Nasl,hl+1,pomZ); if hl+1 = pomZ then PisMost(Start,Nasl); { nalezen most v grafu } Z := min(Z,pomZ); { pripadne snizeni hodnoty Z } end; end; end; begin NactiGraf; PredPruchodem; Pruchod(1,0,F); { vzdy je F=0 } end.

P-III-3

  1. Budeme systematicky zkoumat možnosti vítězného tahu v situacích s malým počtem zápalek zbývajících na hromádce. Přitom vždy musíme rozlišit, zda hráč, který je na tahu, dosud odebral sudý nebo lichý počet zápalek. Výsledky pozorování zapíšeme do přehledné tabulky. Čísla v tabulce udávají, jak vypadá správný vítězný tah. Pokud vítězný tah v dané pozici neexistuje,je v tabulce zapsána pomlčka.

    počet zápalek zbývajících na hromádce hráč na tahu již odebral
    sudý početlichý počet
    1 - 1
    2 2 1
    3 2 3
    4 - 3
    5 1 -
    6 1 2
    7 3 2
    8 3 -
    9 - 1
    10 2 1
    11 2 3
    První tři řádky tabulky pro počty zápalek 1, 2 a 3 jsme získali prozkoumáním všech možností povoleného tahu. Další řádky tabulky již zaplňujeme mechanicky, vždy na základě znalosti tří bezprostředně předcházejících řádků. Hráč totiž může svým tahem odebrat 1, 2 nebo 3 zápalky a tím se situace ve hře převede na situaci popsanou právě jedním ze tří předcházejících řádků. Vítězný tah existuje tehdy, jestliže přivede soupeře do situace, v níž on naopak žádný vítězný tah nemá (v tabulce je pomlčka). Při zaplňování tabulky využíváme skutečnost, že víme, zda soupeř dosud odebral sudý nebo lichý počet (to je dáno paritou našeho počtu zápalek a počtu zápalek zbývajících na hromádce, celkem všech zápalek je lichý počet).

    Po zaplnění 11 řádků tabulky zjistíme, že se hodnoty v tabulce začínají opakovat s periodou 8. Vzhledem k tomu, že se zopakovaly tři po sobě jdoucí řádky (řádky 9, 10 a 11 jsou shodné s řádky 1, 2 a 3) a že každý další řádek tabulky sestrojujeme vždy pouze na základě tří bezprostředně předcházejících řádků, je v tuto chvíli jisté, že se obsah tabulky bude i nadále stále opakovat s periodou 8.

    Tím je úloha vyřešena a prvních 8 řádků uvedené tabulky obsahuje přehledně sepsanou vítěznou strategii naší hry. Hráč na tahu zjistí počet zbývajících zápalek modulo 8 a na základě této hodnoty a parity počtu zápalek, které již sám odebral, určí z tabulky, zda má zaručeno vítězství ve hře. Pokud ano, tabulka udává počet zápalek, kolik má odebrat.

    Počáteční počet všech zápalek N musí být lichý. Začínající hráč nemá zatím žádnou odebranou zápalku, tzn. má sudý počet (nula je sudé číslo). Z tabulky plyne, že na začátku hry má začínající hráč zaručeno vítězství při dodržení popsané vítězné strategie, je-li N tvaru 8k+3, 8k+5 nebo 8k+7. Pokud je N tvaru 8k+1, začínající hráč s dobře hrajícím soupeřem prohraje.

  2. Úlohu řešíme zcela stejným způsobem jako úlohu a). Opět sestrojíme tabulku vítězné strategie:
    počet zápalek zbývajících na hromádce hráč na tahu již odebral
    sudý početlichý počet
    1 - 1
    2 2 1
    3 2 3
    4 4 3
    5 4 -
    6 1 -
    7 - 1
    8 2 1
    9 2 3
    10 4 3
    Řádky se v tomto případě začínají opakovat s periodou délky 6. Ověřili jsme zopakovaní čtyř po sobě jdoucích řádků (řádky 7, 8, 9 a 10 jsou shodné s řádky 1, 2, 3 a 4), neboť každý řádek závisí pouze na čtyřech svých předchůdcích. Stejnou úvahou jako v úloze a) z toho plyne, že prvních 6 řádků zde uvedené tabulky obsahuje úplnou vítěznou strategii hry.

    Hráč začínající hru má zajištěno vítězství při dodržení popsané vítězné strategie, je-li počáteční počet zápalek N tvaru 6k+3 nebo 6k+5. Pokud je N tvaru 6k+1, začínající hráč s dobře hrajícím soupeřem prohraje.

P-III-4

  1. Hledaný stroj neexistuje. Důvodem je nejednoznačnost zápisu čísel (vedoucí nuly) a zároveň striktní požadavek na synchronní čtení obou vstupů. Představte si porovnávání dvou zápisů téhož čísla, přičemž jeden obsahuje k cifer, druhý obsahuje před zápisem dalších k nul (tedy celkem 2k cifer). Po přečtení prvních k znaků stroj již dočte první vstup do konce, z druhého však nepřečetl jedinou významnou cifru. To znamená, že si pro úspěšné porovnávání musí být schopen zapamatovat hodnotu celého kratšího operandu. To v paměti konečné velikosti není možné.

  2. Porovnávání je obdobné porovnávání v poziční soustavě o kladném základu. Jen je třeba si uvědomit, že vyšší cifry v sudých řádech představují vyšší hodnotu, zatímco vyšší cifry v lichých řádech nižší hodnotu čísla. Tedy například 11<01 v soustavě o základu (-2). Během porovnávání tedy sledujeme:
    • která z přečtených částí prvního a druhého čísla je větší resp. že obě čísla byla doposud stejná
    • sudost/lichost právě zpracovávané pozice v zápisu čísel
    Stroj tedy bude mít 6 stavů:
    • N (sudá pozice - stejné zápisy)
    • M (lichá pozice - stejné zápisy)
    • A (sudá pozice - první číslo větší)
    • B (lichá pozice - první číslo větší)
    • C (sudá pozice - druhé číslo větší)
    • D (lichá pozice - druhé číslo větší)
    Počáteční stav je N, přechodová funkce následuje. Pro stav K není definováno žádné přechodové pravidlo. Uvědomte si, že porovnávání lze ukončit až po přečtení delšího ze vstupujících čísel.

    stavčtené symboly
    0 0 0 1 1 0 1 1 0 _ 1 _ _ 0 _ 1 _ _
    N M/_ D/_ B/_ M/_ M/_ B/_ M/_ D/_ K/S
    M N/_ A/_ C/_ N/_ N/_ C/_ N/_ A/_ K/S
    A B/_ D/_ B/_ B/_ B/_ B/_ B/_ D/_ K/P
    B A/_ A/_ C/_ A/_ A/_ C/_ A/_ A/_ K/P
    C D/_ D/_ B/_ D/_ D/_ B/_ D/_ D/_ K/D
    D C/_ A/_ C/_ C/_ C/_ C/_ C/_ A/_ K/D

  3. Stroj neexistuje. Zdůvodnění je zcela analogické úloze prvního kola P-I-4 c.

  4. Sčítání je podobné sčítání v pozičních soustavách o kladném základu. Jen je třeba dát si pozor na přenosy. Kromě skutečnosti, že přenos do vyššího řádu mění znaménko, je třeba mít na zřeteli, že se přenos může projevit nejen v následujícím řádu, ale ve dvou následujících řádech. Tomu je třeba věnovat pozornost na konci sčítání - v situaci, kdy jsou oba operandy dočteny a vypisujeme cifry, které přibyly v důsledku přenosu.

    Přenos může nabývat tří hodnot: označme je 0,1,11 (to jsou hodnoty, které je třeba přičíst k vyšším řádům ve výsledku). Budou jim odpovídat stavy N,J,T. Stav K slouží pouze pro ukončení výpočtu. Počátečním stavem je N.

    stavčtené symboly
    0 0 0 1 1 0 1 1 0 _ 1 _ _ 0 _ 1 _ _
    N N/0 N/1 N/1 T/0 N/0 N/1 N/0 N/1 K/_
    J N/1 T/0 T/0 T/1 N/1 T/0 N/1 T/0 K/1
    T J/1 N/0 N/0 N/1 J/1 N/0 J/1 N/0 J/1

  5. Při určování zbytků po celočíselném dělení záporných čísel se někdy uvažují nezáporné zbytky a někdy záporné (např. (-5)/3 dává zbytek 1 nebo -2). Je možné zvolit si kteroukoli z obou možností, my si zvolíme první z nich. Uvědomme si, že všechny mocniny čísla -2 dávají při dělení třemi zbytek 1. Jako kritérium dělitelnosti třemi může proto posloužit dělitelnost třemi ciferného součtu čísla. Navrhnout stroj, který zjistí, zda ciferný součet čísla je dělitelný třemi, je snadné. Postačí čtyři stavy, z nichž stav K je využit pouze pro ukončení výpočtu. Počáteční stav je N.

    stav čtený symbol
    0 1 _
    N N/_ J/_ K/A
    J J/_ D/_ K/N
    D D/_ N/_ K/N

  6. Hledaný stroj neexistuje. Tato skutečnost vypadá poněkud paradoxně v souvislosti s kladným řešením bodu e. Určit zbytek při celočíselném dělení je ovšem snazší činnost než určit podíl.

    Předpokládejme, že stroj, který dělí třemi, existuje. Uvažujme tyto dělence a jejich podíly při dělení třemi: 10000...0000011 / 3 = 0010101...010101 a 10000...0000110 / 3 = 1101010...101010. Zápisy všech uvedených čísel obsahují (2k+3) cifer, k je libovolné celé kladné číslo. V zápisu dělenců se opakují nuly, v zápisu podílů se opakuje skupina 01 či 10. Výsledky výpočtů nad uvedenými dvěma vstupy se liší již ve druhé číslici zpředu (nepočítáme vedoucí nuly). Zda má být druhou platnou číslicí jednička či nula však stroj zjistí až po přečtení posledních tří cifer vstupujícího čísla. To znamená, že v okamžiku, kdy stroj zapisuje druhou nenulovou cifru výsledku, má již přečten celý vstup (případně až na poslední dvě cifry). Potom by měl ještě vypsat zbytek výstupu. K tomu si ale musí pamatovat přinejmenším počet cifer, které má do výsledku zapsat, na což mu pro dostatečně dlouhé operandy konečná paměť nemůže stačit.