Matematická olympiáda – kategorie P

Řešení úloh domácího kola 43. ročníku

P-I-1

V zadání úlohy je stanoveno, že neznáme žádné předběžné omezení hodnoty N a že N může být vysoké. Tato skutečnost nám zakazuje použít v řešení úlohy pole, do něhož bychom si uložili všechna čísla posloupnosti. Podobné pole by také bylo naprosto zbytečné, k vyřešení úlohy nám bude stačit konstantní paměťový prostor (nezávislý na N). Optimální algoritmus řešení, který zde uvedeme, má lineární časovou složitost. Lepší řešení nemůže existovat, neboť každé z daných N čísel je třeba jednou přečíst a zpracovat.

Postup řešení úlohy je následující. Postupně budeme číst za vstupu jednotlivá čísla tvořící zadanou posloupnost a budeme je vyhodnocovat takovým způsobem, aby v následujících pomocných proměnných byly stále aktuálně uloženy uvedené údaje:

Na začátku výpočtu přečteme první číslo posloupnosti a dosadíme do proměnných vhodné počáteční hodnoty odpovídající tomu, že zatím známe první hladký úsek délky 1 tvořený prvním číslem posloupnosti. Po přečtení každého čísla posloupnosti jsme schopni s využitím zaznamenaných údajů aktualizovat hodnoty všech zde uvedených proměnných. Po zpracování všech N čísel bude výsledek uložen v proměnné MAX. Způsob zpracování každého čísla je již zřejmý z programu.

program Hladky_Usek; var N:integer; {počet čísel v posloupnosti} Cislo:integer; {právě přečtené číslo} Predchozi:integer; {předchozí číslo} Index:integer; {pořadové číslo přečteného čísla} Hladky:integer; {index začátku aktuálního hladkého úseku čísel v posloupnosti} Konstantni:integer; {index začátku aktuálního konstant. úseku čísel v posloupnosti} H1:integer; {menší z hodnot v aktuálním úseku} H2:integer; {větší z hodnot v aktuálním úseku} Max:integer; {délka maximálního hladkého úseku} I:integer; {počítadlo přečtených čísel} begin read(N); read(Cislo); Index:=1; Hladky:=1; Konstantni:=1; H1:=Cislo; Max:=1; for I:=2 to N do begin Predchozi:=Cislo; read(Cislo); Index:=Index+1; if Hladky=Konstantni then {aktuální hladký úsek je zatím tvořen čísly jedné hodnoty} begin if Cislo=H1+1 then begin H2:=Cislo; Konstantni:=Index end else if Cislo=H1-1 then begin H2:=H1; H1:=Cislo; Konstantni:=Index end else if Cislo<>H1 then {konec hladkého úseku} begin if Index-Hladky>Max then Max:=Index-Hladky; Hladky:=Index; Konstantni:=Index; H1:=Cislo end end else {aktuální úsek je tvořen čísly H1 a H2, kde H2=H1+1} begin if (Cislo=H1) or (Cislo=H2) then begin if Cislo<>Predchozi then Konstantni:=Index end else {konec hladkého úseku} begin if Index-Hladky>Max then Max:=Index-Hladky; if (Cislo=H2+1) and (Predchozi=H2) then {v novém hladkém úseku se využije závěrečný úsek předcházejícho hladkého úseku (úseky se překrývají)} begin H1:=H2; H2:=Cislo; Hladky:=Konstantni end else if (Cislo=H1-1) and (Predchozi=H1) then {v novém hladkém úseku se využije závěrečný úsek předcházejícho hladkého úseku (úseky se překrývají)} begin H2:=H1; H1:=Cislo; Hladky:=Konstantni end else begin H1:=Cislo; Hladky:=Index end; Konstantni:=Index end end end; if Index-Hladky+1>Max then {ošetření případu, že by maximální hladký úsek byl na samém konci zadané posloupnosti čísel} Max:=Index-Hladky+1; writeln(Max) end. Popsaný postup řešení je pro každá vstupní data jistě konečný, neboť počet opakování jediného cyklu v algoritmu je pevně určen délkou vstupní posloupnosti čísel. Odtud také plyne již zmíněná lineární časová složitost algoritmu.

Správnost řešení vyplývá ze způsobu zpracování čísel. V každé posloupnosti čísel jistě existuje nějaký hladký úsek, přinejmenším každé číslo samo tvoří jednoprvkový hladký úsek. V konečné posloupnosti čísel je hladkých úseků jenom konečně mnoho, takže některý (případně některé) z nich má maximální délku. Tento úsek bude algoritmem jistě nalezen a jeho délka bude uložena do výsledné proměnné MAX. V proměnné MAX se totiž průběžné počítá maximum ze všech hodnot proměnné HLADKY, tj. ze všech délek hladkých úseků v dané posloupnosti, a proměnná HLADKY obsahuje v každém okamžiku délku co nejdelšího hladkého úseku, který končí u právě přečteného čísla posloupnosti.

P-I-2

Úloha P-I-2 je jednou z klasických úloh teorie grafů. Silniční síť představuje souvislý neorientovaný ohodnocený graf, v němž vrcholy grafu odpovídají městům, hrany grafu silnicím a ohodnocením hran jsou délky jednotlivých silnic. Úkolem potom je nalézt minimální kostru daného grafu.

Různé algoritmy řešení této úlohy lze nalézt v každé základní učebnici diskrétní matematiky nebo teorie grafů. Můžeme použít například tzv. hladový algoritmus. Před jeho uvedením si ještě připomeňme, že libovolnou kostru souvislého grafu získáme vynecháním co možná největšího počtu hran tak, aby graf zůstal souvislým. Graf o N vrcholech může mít více různých koster, každá z nich obsahuje přesně N-1 hran. Z minimality počtu hran plyne, že kostra neobsahuje žádné cykly (tzn. mezi každou dvojicí vrcholů existuje jediná cesta). Minimální kostrou grafu nazýváme takovou kostru grafu, v níž je součet ohodnocení hran minimální. Graf může mít více různých minimálních koster, v takovém případě hledáme jednu libovolnou z nich.

Při řešení úlohy postupujeme následovně. Všechny hrany daného grafu uspořádáme podle jejich ohodnocení vzestupně. Na pořadí hran stejné délky nezáleží. Potom postupně bereme jednotlivé hrany od nejkratší k nejdelší a pro každou z nich zkoumáme, zda ji můžeme zařadit do vytvářené kostry, tj. zda by jejím přidáním do kostry nevzniknul v kostře cyklus. Pokud cyklus nevznikne, hranu do kostry zařadíme, v opačném případě ji vynecháme. Celý výpočet ukončíme ve chvíli, kdy jsme do kostry již zařadili potřebných N-1 hran.

K efektivnímu naprogramování uvedeného algoritmu je třeba zvolit vhodnou datovou reprezentaci. Graf je zadán seznamem hran a jejich ohodnocením. Vzhledem k tomu, že potřebujeme všechny hrany setřídit, použijeme této podoby i pro vnitřní reprezentaci grafu v programu. Ve stejném tvaru, tj. jako seznam hran, budeme vytvářet a ukládat (nebo přímo tisknout) i výslednou kostru.

Zbývá nám poslední a nejtěžší úkol: Potřebujeme mít možnost během výpočtu snadným způsobem testovat, kterou hranu lze přidat do vytvářené kostry. Bylo by dost pracné a pomalé procházet vždy celý seznam hran již zařazených do kostry a nějak zkoumat, zda společně s právě zpracovávanou hranou netvoří cyklus. Lepší je vytvořit si nějakou pomocnou datovou strukturu, v níž bude zaznamenáno, které vrcholy grafu jsou již pospojovány hranami zařazenými do kostry. Postupně vytvářená kostra je nesouvislým podgrafem původního grafu, přičemž každým zařazením další hrany do kostry se o 1 sníží počet komponent souvislosti. Na začátku výpočtu není v kostře ještě žádná hrana a každý vrchol grafu je izolovaný (tvoří vlastní komponentu souvislosti). Po zařazení všech N-1 hran do kostry bude pospojováno všech N vrcholů do souvislého grafu bez cyklů.

Evidenci průběžně vytvářených komponent souvislosti (tj. skupin již pospojovaných vrcholů) je možné programově realizovat různými způsoby. Jednoduchým a názorným řešením (i když z hlediska efektivity ne tím zcela nejlepším) je použít pomocné jednorozměrné pole velikosti N indexované čísly vrcholů od 1 do N. V tomto poli bude pro každý vrchol uloženo číslo komponenty, do níž momentálně náleží. Při zpracování každé další hrany pak snadno otestujeme, zda její krajní vrcholy jsou již v téže komponentě souvislosti. Pokud ano, zkoumanou hranu vynecháme, v opačném případě ji zařadíme do kostry. Při zařazení nové hrany do kostry musíme samozřejmě opravit také naši evidenci pospojovaných vrcholů, neboť tím zároveň dojde k propojení dvou dosud samostatných komponent souvislosti. Všem vrcholům obou těchto komponent musíme proto přiřadit stejné číslo komponenty souvislosti (například jedno z čísel právě spojovaných komponent).

program Minimalni_Kostra; const MaxN=100; {maximální počet měst} MaxSilnic=1000; {maximální počet silnic} type Silnice=record M1,M2,Delka:integer {čísla měst, délka silnice} end; var Sit:array[1..MaxSilnic] of Silnice; {silniční síť} Komponenta:array[1..MaxN] of integer; {čísla komponent} N:integer; {počet měst} S:integer; {počet silnic} PomSilnice:Silnice; {pomocné pro třídění} K1,K2:integer; {čísla komponent} I,J,K:integer; begin {Vstup dat: write('Počet měst: '); readln(N); writeln('Silnice: ODKUD KAM DÉLKA'); S:=0; while not eof do begin S:=S+1; with Sit[S] do read(M1,M2,Delka) end; writeln; writeln('Vybrané silnice:'); {Setřídění silnic v poli Sit[1..S] podle délky od nejkratší k nejdelší. Pro jednoduchost je zde použit algoritmus přímého výběru s kvadratickou časovou složitostí, třídění lze ovšem provést jiným, efektivnějším algoritmem} for I:=1 to S-1 do begin K:=I; for J:=I+1 to S do if Sit[J].Delka<Sit[K].Delka then K:=J; {nalezení nejkratší silnice} if K<>I then begin {prohození silnic na pozicích I a K} PomSilnice:=Sit[K]; Sit[K]:=Sit[I]; Sit[I]:=PomSIlnice end end; {Nalezení minimální kostry:} for I:=1 to N do Komponenta[I]:=I; I:=0; {číslo zkoumané hrany} K:=0; {počet hran v kostře} while K<N-1 do begin I:=I+1; K1:=Komponenta[Sit[I].M1]; K2:=Komponenta[Sit[I].M2]; if K1<>K2 then {silnici Sit[I] zařadit do kostry} begin K:=K+1; writeln(Sit[I].M1:5,Sit[I].M2:5); for J:=1 to N do if Komponenta[J]=K2 then Komponenta[J]:=K1 {spojení komponent, do nichž patří krajní vrcholy} end end end. Důkaz správnosti uvedeného algoritmu je matematicky trochu obtížnější. Postup výpočtu je jistě konečný, neboť nejprve se setřídí podle velikosti konečně mnoho hran a potom se vytváří kostra postupným zkoumáním jednotlivých hran. Počet kroků tohoto procesu je tedy omezen počtem hran. Složitost testování každé hrany, zda ji můžeme přidat do kostry, je konstantní díky pomocné evidenci komponent souvislosti, přidání hrany do kostry pak vyžaduje projít pomocným polem, tj. provést výpočet délky rovnající se počtu vrcholů. Odtud také přímo plyne časová složitost algoritmu. Označíme-li počet hran v grafu (tj. počet silnic) H, setřídění H hodnot podle velikosti můžeme provést jednoduchým třídicím algoritmem složitosti O(H2), jako jsme to provedli v našem programu, nebo lepším třídicím algoritmem, přinejlepším však s časovou složitostí O(H log H). Vlastní hladový algoritmus potom vyžaduje maximálně H kroků, z nichž každý může mít složitost N (kde N je počet vrcholů grafu, tj. počet měst).

Z uvedeného postupu řešení je zřejmé, že algoritmus vyhledá nějakou kostru zadaného grafu. Postupně totiž do vytvářené kostry zařazuje jen takové hrany, jejichž přidáním nevznikne cyklus, a zařadí jich tam maximální možný počet N-1. Zbývá ukázat, že nalezená kostra je skutečně minimální. Hrany tvořící nalezenou kostru pro potřeby důkazu označíme e1, e2,..., ek, kde k=N-1, v pořadí v jakém byly vybírány, tzn. podle velikosti od nejmenší k největší. Každý graf má jistě nějakou minimální kostru (může jich mít i více různých), neboť má konečně mnoho koster a z nich lze vybrat kostru s minimálním ohodnocením. Uvažujme jednu libovolnou minimální kostru, uspořádejme její hrany podle velikosti od nejmenší k největší a označme je po řadě f1, f2, ..., fk. Dokážeme, že pro každé i od 1 do k platí, že ohodnocení hrany eimusí být menší nebo rovno ohodnocení hrany fi. Odtud již přímo plyne, že součet ohodnocení všech hran e1, e2, ..., ek není větší než součet ohodnocení hran f1, f2, ..., fk a že tedy kostra nalezená naším algoritmem je minimální.

Důkaz provedeme sporem. Předpokládejme, že pro nějaké i mezi 1 a k platí, že ohodnocení eije ostře větší než ohodnocení hrany fi. Jistě i>1, neboť za e1jsme v algoritmu vzali hranu s minimálním ohodnocením. Uvažujme množiny hran Ei-1={e1, ...,ei-1} a Fi={f1,...,fi}. Obě tyto množiny hran jsou podmnožinami nějakých koster a proto neobsahují žádný cyklus. K dokončení důkazu stačí ukázat, že v množině Fiexistuje taková hrana f, že Ei-1U{f} neobsahuje cyklus. Všechny hrany obsažené v množině Fi mají totiž ostře menší ohodnocení než hrana ei(to plyne z předpokladu našeho důkazu a z uspořádání množiny Fi), tedy i hrana f má ohodnocení menší než hrana ei. Popsaný algoritmus nalezení minimální kostry by tudíž jako v pořadí i-tou zařadil do vytvářené kostry hranu f místo hrany ei, což je spor.

Existence hrany f, která je prvkem Fi, takové, že Ei-1U{f} neobsahuje cyklus, přímo vyplývá ze skutečnosti, že množina Fi obsahuje o jednu hranu více než množina Ei-1. Uvážíme-li souvislé komponenty grafu určené množinou hran Ei-1 (žádná z těchto komponent neobsahuje cyklus), jistě existuje hrana z Fi spojující dvě různé komponenty - a to je hledaná hrana f. V opačném případě by totiž každá hrana z Fi musela spojovat dvojici vrcholů téže komponenty, a protože v Fi je o jednu hranu více než v Ei-1, nutně by tak něktará skupina hran z Fi vytvořila cyklus.

P-I-3

  1. Nejprve se pokusíme hlouběji proniknout do průběhu uvedené hry tím, že budeme sledovat situaci pro malé počty zápalek zbývající na hromádce:
    • zbývá 0 hráč na tahu prohrává (nemůže brát)
    • zbývá 1 hráč na tahu prohrává (nemůže brát)
    • zbývá 2 hráč na tahu prohrává (nemůže brát)
    • zbývá 3 hráč na tahu vyhrává (vezme 3)
    • zbývá 4 hráč na tahu vyhrává (vezme 3)
    • zbývá 5 hráč na tahu vyhrává (vezme 3 nebo 5)
    • zbývá 6 hráč na tahu vyhrává (vezme 5)
    • zbývá 7 hráč na tahu vyhrává (vezme 5)
    • zbývá 8 hráč na tahu prohrává (odebráním 3 nebo 5 se soupeř dostane do pozice s vyhrávajícím tahem)

    Po vyšetření dalších pozic zjistíme, že vyhrané a prohrané pozice se pravidelně opakují (s periodou délky 8). Na základě provedeného rozboru hry můžeme vyslovit následující hypotézu. Je-li N tvaru 8k, 8k+1 nebo 8k+2, začínající hráč nemůže proti dobrému soupeři vyhrát. Pro ostatní hodnoty N má naopak začínající hráč jisté vítězství, bude-li se držet vítězné strategie. Pro N tvaru 8k+3 nebo 8k+4 musí brát 3 zápalky, pro N tvaru 8k+6 nebo 8k+7 musí brát 5 zápalek, je-li N tvaru 8k+5, může hrát libovolně.

    Správnost vyslovené hypotézy musíme ovšem ještě pořádně dokázat. Je-li počáteční hodnota N tvaru 8k+3, 8k+4, 8k+5, 8k+6 nebo 8k+7 a zahrajeme-li svůj tah podle uvedené strategie, dostane se náš soupeř vždy do situace, že má brát z hromádky obsahující 8k, 8k+1 nebo 8k+2 zápalek. Ať zahraje jakkoliv, po jeho tahu zbyde na hromádce opět počet zápalek tvaru 8k+3, 8k+4, 8k+5, 8k+6 nebo 8k+7 (samozřejmě pro hodnotu k o 1 menší než dříve). Tak se situace opakuje pro stále se zmenšující hodnoty k, každým tahem naším a soupeřovým se k sníží o 1. Po konečném počtu tahů bude proto k nulové a soupeř bude na tahu v pozici s 0, 1 nebo 2 zápalkami na hromádce, což znamená jeho prohru.

    Naopak, pro počáteční počet zápalek N tvaru 8k, 8k+1 nebo 8k+2 vede jakýkoliv tah začínajícího hráče do pozice s 8k+3, 8k+4, 8k+5, 8k+6 nebo 8k+7 zápalkami na hromádce (hodnota k je zde opět o 1 menší) a bude-li se pak náš soupeř držet uvedené strategie, má jisté vítězství ve hře.

  2. Úlohu řešíme zcela analogicky jako úlohu a). Na základě rozboru situací s malým počtem zápalek zbývajících na hromádce dojdeme k následující hypotéze. Je-li na hromádce počet zápalek tvaru 10k, 10k+1, 10k+2 nebo 10k+6, začínající hráč prohraje, pokud bude jeho soupeř hrát dobře. Pro ostatní hodnoty N má naopak hráč na tahu jisté vítězství při dodržování této vítězné strategie: pro N tvaru 10k+3, 10k+4 a 10k+5 musí vzít 3 zápalky, pro N tvaru 10k+7, 10k+8 a 10k+9 bere 7 zápalek. Hypotézu dokážeme stejnou úvahou jako v řešení úlohy a).

P-I-4

Většinu početních postupů, které jsme se učili na základní škole provádět, lze konečným sekvenčním strojem přímočaře modelovat. Řešení úloh b),d),e),f) by vás proto mělo napadnout poměrně rychle.

  1. Ačkoli čísla podle velikosti porovnáváme častěji odzadu (tak totiž máme zaručeno, že budeme porovnávat cifry odpovídajících si řádů), existuje i jednoduchý algoritmus, jak je porovnávat odpředu. Výsledek stroj ohlásí až po dočtení vstupních sledů, během výpočtu se přitom musíme připravit na dvě možné situace:
    • oba zápisy budou stejně dlouhé. V tom případě si potřebujeme pamatovat rozdíl na prvním místě zpředu, kde se zápisy lišily.
    • oba zápisy budou různě dlouhé. Pak můžeme o větším čísle rozhodnout pouze na základě délky zápisu. Není podstatné, jaké číslice obsahovaly oba zápisy, a tedy z průběhu výpočtu si v tomto případě nepotřebujeme nic pamatovat.
    Která z těchto možností nastává, však zjistíme až po přečtení kratšího z obou čísel (resp. obou). Během výpočtu proto musíme rozlišovat 3 možné situace:
    • zápisy se zatím nelišily
    • na prvním místě, kde se lišily, bylo první číslo větší
    • na prvním místě, kde se lišily, bylo druhé číslo menší
    Navržený stroj proto bude mít stavy N,A,B, které budou přesně odpovídat výše uvedeným situacím. Pro potřeby ukončení budeme ještě potřebovat další stav K (pro něj nebude definováno žádné přechodové pravidlo). Počátečním stavem je N, přechodová funkce je dána tabulkou. Řádky v tabulce jsou označeny původním stavem, sloupce jsou označeny čteným symbolem z prvního resp. druhého sledu. Údaj před lomítkem je nový stav, za lomítkem je uveden vypisovaný znak.

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

  2. Porovnávat zápisy čísel odzadu je běžná operace. Podobně jako v úloze a) si v průběhu výpočtu potřebujeme pamatovat, zda se již zápisy čísel lišily. Pokud ano, musíme si pamatovat, které z čísel obsahuje vyšší cifru na místě, kde byla odlišnost zjištěna naposled. Pamatujeme si tedy pouze odlišnost v dosud nejvyšším testovaném řádu, odlišnosti v nižších řádech už na výsledek porovnání nemohou mít vliv.

    Stroj bude mít 4 stavy:

    • N..zápisy čísel se zatím nelišily
    • A..první číslo obsahovalo větší cifru
    • B..druhé číslo obsahovalo větší cifru
    • K..pomocný stav pro ukončení výpočtu.
    Počáteční stav je N.

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

  3. Úloha není konečným sekvenčním strojem řešitelná. Uvažujme výpočty nad vstupními sledy o délce k cifer 1011.....11 a 1000.....01 a 1011.....11 a 1000.....00. Do doby, než stroj ze vstupních sledů přečte poslední cifry, může na výstup zapsat pouze 10, protože další cifra výstupu závisí na posledních cifrách vstupů. Po dočtení vstupů pak bude muset vypsat ještě k-1 dalších cifer (nul či jedniček). V případě, kdy délka vstupů k je větší než počet vnitřních stavů stroje, si stroj není schopen pomocí vnitřních stavů zapamatovat, kolik znaků má po přečtení posledních cifer ze vstupu ještě vypsat.

  4. Jde o běžné sčítání čísel v poziční soustavě. Pro výpočet stačí dva stavy, P (je přenos z nižších řádů) a B (bez přenosu). Počátečním stavem je B.

    stavčtené symboly
    0 00 11 01 10 _1 __ 0_ 1_ _
    BB/0B/1B/1P/0B/0B/1B/0B/1 -
    PB/1P/0P/0P/1B/1P/0B/1P/0B/1

  5. Řešení části e) lze získat jednoduchou modifikací stroje z řešení úlohy f).

  6. Stroj bude simulovat písemné dělení. Postupujeme od nejvyšších řádů k nižším. Pomocí vnitřních stavů si pamatujeme dosavadní zbytek při dělení (N nula, J jedna, D dva). V jednom kroku výpočtu "sepíšeme" další cifru, zapíšeme jednu cifru do podílu a určíme nový dílčí zbytek. Po dočtení vstupního čísla do konce bude vypsán podíl, zbytek bude určen vnitřním stavem. Je třeba si dát pozor na to, že zápis výsledku musí začínat jedničkou, ale tuto nepatrnou technickou komplikaci snadno vyřešíme: přidáme nové dva stavy X,Y. Stroj má celkem pět stavů, počáteční stav je X.

    stavčtený symbol
    0 1 _
    X - Y/_ -
    Y D/_ N/1 -
    N N/0 J/0 -
    J D/0 N/1 -
    D J/1 D/1 -