Matematická olympiáda – kategorie P

Řešení úloh oblastního kola 43. ročníku

P-II-1

Úloha je zobecněním úlohy P-I-1 z domácího kola. Postup řešení je zcela analogický, potřebujeme pouze trochu složitější průběžnou evidenci informací o dané posloupnosti čísel.

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 paměťový prostor úměrný hodnotě K (nezávislý na N), tzn. vzhledem k uvedenému omezení přípustných hodnot K vlastně prostor konstantní velikosti. 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 ve vhodně zvolené sadě pomocných proměnných byly stále aktuálně uloženy správné údaje charakterizující již přečtenou část vstupní posloupnosti čísel. Důležité je průběžně si udržovat informace o právě zkoumaném K-hladkém úseku: kde začíná, jaké hodnoty čísel obsahuje a hlavně, na kterém místě v posloupnosti se naposledy vyskytla každá z těchto hodnot. Pro uložení poslední uvedené informace potřebujeme pole velikosti K+1, neboť každý K-hladký úsek může obsahovat nejvýše K+1 různých hodnot. Údaje z tohoto pole jsou důležité proto, že se K-hladké úseky mohou částečně překrývat. Při ukončení zkoumaného úseku potom můžeme určit, kde začíná další K-hladký úsek, aniž by bylo třeba nějak se vracet v dané posloupnosti čísel. Evidence potřebných údajů může být následující:

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 další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é MAXUSEK. Způsob zpracování každého čísla je již zřejmý z programu, kde jsou uvedeny vysvětlující komentáře.

program Max_K_hladky_Usek; const MaxK=10; {maximální možná hodnota K} var N:integer; {počet čísel v posloupnosti} K:0..MaxK; {stupeň "hladkosti"} Cislo:integer; {přečtené číslo} MinHodnota:integer; {minimální hodnota čísel v aktuálním hladkém úseku} MaxHodnota:integer; {maximální hodnota čísel v aktuálním hladkém úseku} NovaMezHodnota:integer; {nová max. nebo min. hodnota v aktuálním hladkém úseku} Index:integer; {index právě přečteného čísla} Hladky:integer; {index začátku aktuálního hladkého úseku} Posledni:array[0..MaxK] of integer; {index posledního výskytu jednotlivých hodnot MinHodnota..MaxHodnota v aktuálním hladkém úseku} Posun:integer; {posun hodnot v hladkém úseku} MaxUsek:integer; {délka max. K-hladkého úseku} I,J:integer; begin write('Počet čísel v posloupnosti N: '); readln(N); write('Stupeň hladkosti K: '); readln(K); read(Cislo); {první číslo dané posloupnosti} Index:=1; Hladky:=1; MaxUsek:=1; MinHodnota:=Cislo; MaxHodnota:=Cislo; Posledni[0]:=1; {úsek tvořen jen prvním číslem} for J:=2 to N do begin read(Cislo); Index:=Index+1; {rozlišíme 6 možností, jaké je další přečtené číslo vzhledem k právě zkoumanému K-hladkému úseku:} if (Cislo>=MinHodnota) and (Cislo<=MaxHodnota) then {nové číslo prodlouží zkoumaný hladký úsek, nezvětší se ani rozsah hodnot čísel v úseku} Posledni[Cislo-MinHodnota]:=Index {zaznamenáme výskyt} else if (Cislo>MaxHodnota) and (Cislo<=MinHodnota+K) then {nové číslo prodlouží zkoumaný hladký úsek, zvětší se jen rozsah hodnot čísel v úseku, a to směrem k vyšším hodnotám} begin for I:=MaxHodnota-MinHodnota+1 to Cislo-MinHodnota-1 do Posledni[I]:=0; Posledni[Cislo-MinHodnota]:=Index; {zaznamenáme výskyt} MaxHodnota:=Cislo {zvětší se MaxHodnota} end else if (Cislo<MinHodnota) and (Cislo>=MaxHodnota-K) then {nové číslo prodlouží zkoumaný hladký úsek, zvětší se jen rozsah hodnot čísel v úseku, a to směrem k nižším hodnotám, je proto nutné posunout údaje uložené v poli Posledni} begin for I:=MaxHodnota-MinHodnota downto 0 do Posledni[I+MinHodnota-Cislo]:=Posledni[I]; for I:=1 to MinHodnota-Cislo-1 do Posledni[I]:=0; Posledni[0]:=Index; {zaznamenáme výskyt} MinHodnota:=Cislo {zmenší se MinHodnota} end else if (Cislo>MaxHodnota+K) or (Cislo<MinHodnota-K) then {nové číslo ukončuje dosud zkoumaný K-hladký úsek a zahajuje nový úsek, tento nový úsek se s předchozím nepřekrývá a bude tudíž zatím tvořen tímto jediným číslem} begin if Index-Hladky>MaxUsek then {kontrola délky úseku} MaxUsek:=Index-Hladky; {nalezen dosud nejdelší} Hladky:=Index; MinHodnota:=Cislo; MaxHodnota:=Cislo; Posledni[0]:=Index {úsek tvořen jedním číslem} end else if Cislo>MaxHodnota then {jistě platí: (Cislo>MinHodnota+K) and (Cislo<=MaxHodnota+K) } {nové číslo ukončuje dosud zkoumaný K-hladký úsek a zahajuje nový úsek, tento nový úsek se s předchozím může částečně překrývat} begin if Index-Hladky>MaxUsek then {kontrola délky úseku} MaxUsek:=Index-Hladky; {nalezen dosud nejdelší} NovaMezHodnota:=Cislo-K; {nová min. hodnota} for I:=0 to NovaMezHodnota-1-MinHodnota do if Posledni[I]>Hladky then Hladky:=Posledni[I]; Hladky:=Hladky+1; {nový začátek K-hladkého úseku} while (NovaMezHodnota<Cislo) and (Posledni[NovaMezHodnota-MinHodnota]<Hladky) do NovaMezHodnota:=NovaMezHodnota+1; Posun:=NovaMezHodnota-MinHodnota; {potřebný posun hodnot v poli Posledni} for I:=Posun to MaxHodnota-MinHodnota do if Posledni[I]<Hladky then Posledni[I-Posun]:=0 {staré výskyty rušíme} else Posledni[I-Posun]:=Posledni[I]; {posun hodnoty} for I:=MaxHodnota-NovaMezHodnota+1 to Cislo-NovaMezHodnota-1 do Posledni[I]:=0; Posledni[Cislo-NovaMezHodnota]:=Index; {zaznamenáme} MinHodnota:=NovaMezHodnota; MaxHodnota:=Cislo end else {jistě platí: (Cislo<MinHodnota) and (Cislo>=MinHodnota-K) and (Cislo<MaxHodnota-K) } {nové číslo ukončuje dosud zkoumaný K-hladký úsek a zahajuje nový úsek, tento nový úsek se s předchozím může částečně překrývat} begin if Index-Hladky>MaxUsek then MaxUsek:=Index-Hladky; NovaMezHodnota:=Cislo+K; {nová max. hodnota} for I:=NovaMezHodnota+1-MinHodnota to MaxHodnota-MinHodnota do if Posledni[I]>Hladky then Hladky:=Posledni[I]; Hladky:=Hladky+1; {nový začátek K-hladkého úseku} while (NovaMezHodnota>Cislo) and (Posledni[NovaMezHodnota-MinHodnota]<Hladky) do NovaMezHodnota:=NovaMezHodnota-1; Posun:=MinHodnota-Cislo; {potřebný posun hodnot v poli Posledni} for I:=NovaMezHodnota-MinHodnota downto 0 do if Posledni[I]<Hladky then Posledni[I+Posun]:=0 {staré výskyty rušíme} else Posledni[I+Posun]:=Posledni[I]; {posun hodnoty} for I:=1 to Posun-1 do Posledni[I]:=0; Posledni[0]:=Index; {zaznamenáme výskyt} MinHodnota:=Cislo; MaxHodnota:=NovaMezHodnota end end; {ještě zbývá provést test, zda nejdelší K-hladký úsek nebyl až na úplném konci posloupnosti:} if Index-Hladky+1>MaxUsek then MaxUsek:=Index-Hladky+1; writeln(MaxUsek) 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 pro libovolné K nějaký K-hladký úsek, přinejmenším každé číslo samo tvoří jednoprvkový K-hladký úsek. V konečné posloupnosti čísel je K-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é MAXUSEK. V proměnné MAXUSEK se totiž průběžné počítá maximum ze všech hodnot INDEX-HLADKY před každým zvýšením hodnoty proměnné HLADKY, tj. ze všech délek již neprodloužitelných K-hladkých úseků v dané posloupnosti.

P-II-2

Úloha P-II-2 je drobnou modifikací jedné 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. Úkolem je zjistit, zda je doplněk daného grafu bipartitní.

Postup řešení úlohy si můžeme názorně představit tak, že při rozdělování měst do skupin budeme jednotlivá města "obarvovat" dvěma barvami podle toho, do které skupiny bylo město zařazeno. Městům zařazeným do první skupiny přiřadíme barvu 1 a městům z druhé skupiny barvu -1. Na začátku výpočtu není žádné město nijak obarveno, neboť dosud nebylo zařazeno do žádné ze skupin.

Celý proces rozdělování měst do skupin zahájíme tím, že jedno libovolné město (zde město s číslem 1) obarvíme barvou 1. Města, do kterých z tohoto města nevede přímá silnice, nesmí podle zadání patřit do stejné skupiny. Obarvíme je proto barvou -1. Podobně postupujeme stále dál. Obecně platí, že bylo-li nějaké město zařazeno do jedné ze skupin, musí být všechna města, která s ním nejsou spojena přímou silnicí, zařazena do opačné skupiny. Přitom musíme průběžně kontrolovat, zda nedojde ke konfliktu. Konflikt nastane tehdy, potřebujeme-li nějaké již obarvené město obarvit opačnou barvou. V takovém případě rozdělení měst do skupin neexistuje a výpočet ihned ukončíme. Jinak pokračujeme v obarvování měst tak dlouho, dokud jsme nuceni obarvovat další města (vlastně jako důsledek počátečního obarvení prvního města). Jestliže se tento proces zastaví a přitom ještě existují neobarvená města, můžeme jedno libovolné z nich (zde to s nejmenším číslem) obarvit libovolnou barvou (zde barvou 1) a pokračujeme pak v obarvování stejným způsobem. Celé rozdělování měst skončí ve chvíli, kdy jsou všechna města obarvena a zkontrolována, zda jejich obarvení nezpůsobuje žádný konflikt (obarvení měst pak určuje jedno možné rozdělení měst do skupin) nebo když při obarvování dojde ke konfliktu (rozdělení měst v takovém případě neexistuje).

Pro efektivní naprogramování uvedeného postupu je důležitá vhodná volba datových struktur. Informace o existujících silnicích uložíme do čtvercového pole A logických hodnot velikosti N x N (tj. vytvoříme matici sousednosti zkoumaného grafu). Pro evidenci obarvení měst, tj. zařazení měst do skupin, použijeme jednorozměrné pole Barva indexované čísly měst od 1 do N. Neobarvená města budou mít v tomto poli přiřazenu hodnotu 0, obarvená pak hodnotu 1 nebo -1 podle zvolené barvy. Dále potřebujeme udržovat si seznam čísel měst, která jsme již obarvili, ale dosud jsme nezajistili, aby města, do kterých nevede přímá silnice, patřila do opačné skupiny. Pro uložení tohoto seznamu použijeme jednorozměrné pole Seznam o N prvcích.

Z uvedeného postupu již plyne správnost algoritmu. Postupem obarvování je zajištěno, že se nikdy nemohou dostat do téže skupiny dvě města, mezi nimiž nevede přímá silnice. Pokud tedy nalezneme bez konfliktu obarvení všech měst, určuje toto obarvení správné rozdělení měst do skupin. Naopak, konflikt nastane jedině ve chvíli, kdy by již obarvené město mělo být zařazeno do opačné skupiny, než kam bylo dříve zařazeno, tj. když rozdělení měst do skupin neexistuje. Konečnost výpočtu je dána tím, že v každém kroku je obarveno jedno město. Počet kroků výpočtu je tedy roven nejvýše počtu všech měst N. Odtud plyne, že časová složitost algoritmu je úměrná N2, neboť každý krok výpočtu představuje provedení řádově N operací (jeden průchod přes všech N měst).

program Rozdeleni_Mest; const MaxN=100; {maximální možný počet měst} var A:array[1..MaxN,1..MaxN] of Boolean; {matice silnic} Barva:array[1..MaxN] of -1..1; {rozdělení měst} Seznam:array[1..MaxN] of 1..MaxN; {pracovní seznam měst} Posledni:0..MaxN; {index posledního prvku seznamu} N:integer; {počet měst} Zarazena:integer; {počet měst zařazených do skupin} Konflikt:Boolean; {města nelze rozdělit} I,J:integer; begin {Vstup dat:} write('Počet měst: '); readln(N); for I:=1 to N do begin for J:=1 to N do A[I,J]:=false; Barva[I]:=0 end; write('Seznam všech silnic'); writeln(' - každá je zadána dvojicí čísel měst ODKUD a KAM vede:'); while not eof do begin read(I,J); A[I,J]:=true; A[J,I]:=true end; {Rozdělování měst:} Seznam[1]:=1; {výchozí město} Posledni:=1; {v seznamu zařazených je zatím samo} Barva[1]:=1; {zařazeno do skupiny 1} Zarazena:=1; {jedno město je zařazeno} Konflikt:=false; while (Posledni>0) and not Konflikt do begin I:=Seznam[Posledni]; Posledni:=Posledni-1; for J:=1 to N do if (J<>I) and not A[I,J] then if Barva[J]=Barva[I] then Konflikt:=true else if Barva[J]=0 then begin Barva[J]:=-Barva[I]; Posledni:=Posledni+1; Seznam[Posledni]:=J; Zarazena:=Zarazena+1 end; if (Posledni=0) and (not Konflikt) and (Zarazena<N) then begin {libovolné dosud nezařazené město můžeme zařadit do kterékoliv skupiny -> první dosud nezařazené dáme do skupiny 1} J:=1; while Barva[J]<>0 do J:=J+1; Seznam[1]:=J; {nově zařazené město} Posledni:=1; {v seznamu zařazených je nyní samo} Barva[J]:=1; {zařazeno do skupiny 1} Zarazena:=Zarazena+1; {další město je zařazeno} end end; {Vyhodnocení procesu rozdělování měst:} if Konflikt then writeln('Rozdělení měst do dvou skupin neexistuje.') else begin writeln('Rozdělení měst do dvou skupin je možné.'); writeln('Jedno takové přípustné rozdělení vypadá takto:'); write('1.skupina:'); for I:=1 to N do if Barva[I]=1 then write(I:3); writeln; write('2.skupina:'); for I:=1 to N do if Barva[I]=-1 then write(I:3); writeln end end.

P-II-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á
    • zbývá 1 hráč na tahu vyhrává (vezme 1)
    • zbývá 2 hráč na tahu vyhrává (vezme 2)
    • zbývá 3 hráč na tahu prohrává (odebráním 1 nebo 2 se soupeř dostane do pozice s vyhrávajícím tahem)
    • zbývá 4 hráč na tahu vyhrává (vezme 1 nebo 4)
    • zbývá 5 hráč na tahu vyhrává (vezme 2)
    • zbývá 6 hráč na tahu prohrává (odebráním 1, 2 nebo 4 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 3). Na základě provedeného rozboru hry můžeme vyslovit následující hypotézu. Je-li počet zápalek na hromádce N tvaru 3k, 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 3k+1 bude brát 1 zápalku, pro N tvaru 3k+2 vezme 2 zápalky.

    Správnost vyslovené hypotézy nyní dokážeme. Je-li počáteční počet zápalek tvaru 3k+1 nebo 3k+2 a zahrajeme svůj tah podle uvedené strategie, dostane se soupeř do situace, že je na tahu a na hromádce je 3k zápalek. Ať zahraje jakkoliv, po jeho tahu zbude na hromádce počet zápalek, který není dělitelný třemi, tj. počet tvaru 3m+1 nebo 3m+2. Soupeř totiž musí odebrat počet zápalek, který je mocninou 2, a žádná mocnina dvou není beze zbytku dělitelná třemi. Nemůže tudíž svým tahem sebrat poslední zápalku a my se po jeho tahu opět dostaneme do situace, v níž použijeme vítězný tah podle uvedené strategie. Tak se situace opakuje pro stále se zmenšující počet zápalek zbývajících na hromádce. Po konečném počtu tahů budeme na tahu v pozici s 1 nebo 2 zápalkami na hromádce, což znamená již bezprostřední výhru.

    Naopak, pro počáteční počet zápalek N tvaru 3k vede jakýkoliv tah začínajícího hráče do pozice, v níž není počet zápalek zbývajících na hromádce dělitelný třemi. Bude-li se pak náš soupeř držet uvedené strategie, má jisté vítězství ve hře.

  2. Úlohu můžeme řešit zcela analogicky jako úlohu a). Místo postupného zkoumání jednotlivých hodnot N je ovšem lepší nejprve se trochu zamyslet nad paritou (tj. sudostí resp. lichostí) počtu zápalek na hromádce. V jednom tahu se odebírá pokaždé počet zápalek, který je mocninou tří, tedy vždy lichý počet. Po každém tahu jednoho z hráčů se tudíž změní parita počtu zápalek zbývajících na hromádce. Po konečně mnoha tazích se hromádka zcela vyprázdní. Tohoto vítězného stavu dosáhne určitě ten hráč, který je na tahu vždy, když zbývá na hromádce lichý počet zápalek. Odtud již plyne následující závěr: Je-li počáteční počet zápalek lichý, hru vyhraje začínající hráč, při sudém počtu naopak zvítězí ten hráč, který hru nezahajuje. Přitom vůbec nezáleží na tom, jaké počty zápalek hráči ve svých tazích odebírají.

P-II-4

  1. Požadovaný stroj neexistuje. Zdůvodnění je stejné jako v úloze prvního kola P-I-4 c).

  2. Čísla v doplňkovém kódu lze sčítat odzadu stejně jako celá nezáporná čísla v poziční soustavě. V jednom kroku stroj přečte z obou sledů po jedné cifře a zapíše jednu cifru do výsledku. Pomocí vnitřních stavů si bude pamatovat přenos mezi řády. Je však třeba vyřešit technické problémy. Jakmile jedno z čísel skončí, musí stroj počítat stejně, jako by ve vstupním sledu následovaly další cifry rovné naposledy čtené cifře. Jakmile skončí oba sledy, je třeba vypsat ještě alespoň jednu cifru výsledku (zkuste si sečíst 2k+2k).

    Stroj si tedy musí pamatovat tyto informace:

    • zda došlo k přenosu (P=přenos, B=bez přenosu)
    • poslední čtenou cifru v prvním sledu (0 nebo 1)
    • poslední čtenou cifru v druhém sledu (0 nebo 1)
    Stavy stroje budou vlastně představovat trojice informací, celkem jich bude osm. Označíme je B=(B,0,0), C=(B,0,1), D=(B,1,0), Q=(P,0,1), R=(P,1,0), S=(P,1,1). Rozmyslete si, že do stavů (B,1,1) a (P,0,0) se stroj nemůže nikdy dostat. Počáteční stav je B, přechodová funkce je dána tabulkou. Pro stav K není přechodová funkce definována.

    stavčtené symboly
    0 00 11 01 10 _1 __ 0_ 1_ _
    BB/0C/1D/1S/0B/0D/1B/0C/1K/0
    CB/0C/1D/1S/0C/1S/0B/0C/1K/0
    DB/0C/1D/1S/0B/0D/1D/1S/0K/0
    QB/1Q/0R/0S/1Q/0S/1B/1Q/0K/1
    RB/1Q/0R/0S/1B/1R/0R/0S/1K/1
    SB/1Q/0R/0S/1Q/0S/1R/0S/1K/1

  3. Řešme společně s úlohou d. Obdobně jako v prvním kole sestrojíme konečný sekvenční stroj, který bude vstupující číslo dělit třemi. Podíl zapíše do výstupního sledu, zbytek po dělení bude dán stavem, v němž výpočet skončí. Na rozdíl od úlohy v prvním kole odpadá technická starost o případ, kdy by ve výsledku byly nadbytečné vedoucí nuly nebo jedničky. Počátečním stavem je X.

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