Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (1. soutěžní den) 50. ročníku

P-III-1 Věže

Nejdříve je třeba si uvědomit, že jednotlivé souřadnice pozic věží je možno volit nezávisle na sobě. To platí proto, že volba sloupce nijak neomezí rozsah řádek, ve kterém může být věž umístěna. Můžeme tedy nejdříve pro každou věž zvolit sloupec, ve kterém se bude nacházet, a pak pro každou věž zvolit řádek. Převedli jsme tak původní úlohu do jednoho rozměru. Jednotlivé obdélníky se promítnou na intervaly a v každém intervalu chceme nalézt číslo i (umístění věže) takové, aby se čísla žádných dvou intervalů neshodovala.

Čísla budeme hledat následujícím způsobem: Budeme postupně procházet čísla od 1 do N a budeme si udržovat informaci, které intervaly obsahují dané číslo a ještě nemají žádné číslo přiděleno. Z těchto intervalů vybereme ten, který končí nejdříve, a přidělíme mu aktuální číslo. Pokud vybraný interval již neobsahuje přidělované číslo (skončil dříve), úloha nemá řešení. Přímá implementace této myšlenky je samozřejmě možná, ale pomalá (O(N2)). My implementaci zrychlíme následujícím způsobem: Abychom mohli rychle upravovat informace o tom, které intervaly obsahují dané číslo, setřídíme si je nejdříve vzestupně podle jejich počátku. Abychom byli dále schopni rychle nalézt interval, který končí nejdříve, budeme si intervaly obsahující dané číslo uchovávat v haldě srovnané podle konců intervalů. Přidělování čísel tedy ve vylepšené implementaci probíhá následovně: Procházíme všechna čísla od 1 do N. Pro každé číslo přidáme do haldy všechny intervaly začínající na daném čísle. Pak z haldy (pokud je neprázdná) odebereme minimum (tj. nejdříve končící interval) a přidělíme mu aktuální číslo. Pokud interval již neobsahuje aktuální číslo, řekneme, že požadované rozestavení věží neexistuje. S těmito vylepšeními má algoritmus časovou složitost O(N log N) a paměťovou složitost O(N).

Nechť máme nějaké korektní rozestavení věží R. Indukcí dokážeme, že toto rozestavení lze upravit na takové, jaké navrhne náš algoritmus, a tím tedy ukážeme, že náš algoritmus nalezne korektní rozestavení věží.

Program je přímou implementací algoritmu. Halda je implementována v poli, kde prvek na pozici i má syny na pozicích 2i a 2i+1.

program Veze; {P-III-1} const MAXN = 100; type {Popis jednoho intervalu} Int = record s, e : Integer; {Počátek a konec intervalu} n : Integer; {Číslo věže, které interval patří} end; {Popis jednoho bodu} Point = array [1..2] of Integer; {Popis jednoho obdélníka} Rectangle = record a, b : Point; {Levý horní a pravý dolní roh} end; {Intervaly v jedné souřadnici} IntList = array[1..MAXN] of Int; CmpProc = function(A, B : Int) : ShortInt; var N : Integer; {Pocet vezi} Rec : Array[1..MAXN] of Rectangle; {Obdélníky} T : Array[1..MAXN] of Point; {Umístění věží} {Načte vstup} procedure ReadInp; var i : Integer; begin Write('Pocet vezi: '); Read(N); WriteLn('Souradnice obdelniku:'); for i := 1 to N do Read(Rec[i].a[1], Rec[i].a[2], Rec[i].b[1], Rec[i].b[2]); end; {Přidá interval do haldy} procedure AddHeap(var N : Integer; var H : IntList; I : Int; Cmp : CmpProc); var A : Integer; Tmp : Int; begin Inc(N); H[N] := I; A := N; while A <> 1 do begin {Nejsme na vrcholu} if Cmp(H[A], H[A div 2]) <> -1 then {Je splněna podmínka haldy?} break; {Zaměníme prvky, aby byla podmínka splněna} Tmp := H[A]; H[A] := H[A div 2]; H[A div 2] := Tmp; A := A div 2; {Posun o úroveň výše} end; end; {Odebere z haldy minimum} procedure GetHeapMin(var N : Integer; var H : IntList; Cmp : CmpProc; var Res : Int); var A, M : Integer; Tmp : Int; begin Res := H[1]; H[1] := H[N]; Dec(N); A := 1; while A * 2 < N do begin {Nejsme na dně?} {Nalezneme menšího ze synů} if Cmp(H[A*2], H[A*2+1]) = -1 then M := A*2 else M := A*2+1; if Cmp(H[M], H[A]) <> -1 then {Podmínka haldy splněna?} break; {Zaměníme prvky, aby byla podmínka splněna} Tmp := H[M]; H[M] := H[A]; H[A] := Tmp; A := M; {Posun o úroveň níže} end; end; {Porovná dva intervaly podle počátku} function CmpInt(a, b : Int) : ShortInt; far; begin if (a.s < b.s) or ((a.s = b.s) and (a.e < b.e)) then CmpInt := -1 else if (a.s = b.s) and (a.e = b.e) then CmpInt := 0 else CmpInt := 1; end; {Setřídí pole intervalů} procedure SortInts(var A : IntList); var C, i : Integer; H : IntList; begin C := 0; for i := 1 to N do AddHeap(C, H, A[i], CmpInt); for i := 1 to N do GetHeapMin(C, H, CmpInt, A[i]); end; {Srovná intervaly podle konce} function CmpBack(a, b : Int) : ShortInt; far; begin if a.e < b.e then CmpBack := -1 else if a.e = b.e then CmpBack := 0 else CmpBack := 1; end; {Spočte jednu souřadnici pro každou věž} function CountCoord(c : Integer) : Boolean; var Ints : IntList; {Intervaly} i, a : Integer; ActInts : IntList; {Halda intervalů k uplatnění} ActIntsN : Integer; {Počet intervalů v haldě} Tmp : Int; begin {Vytvoří pole intervalů z obdélníku} for i := 1 to N do begin Ints[i].s := Rec[i].a[c]; Ints[i].e := Rec[i].b[c]; Ints[i].n := i; end; SortInts(Ints); {Setřídí intervaly} {Určí souřadnici věží} ActIntsN := 0; a := 1; for i := 1 to N do begin {Přidá do haldy všechny intervaly začínající na aktuální pozici} while (a <= N) and (Ints[a].s = i) do begin AddHeap(ActIntsN, ActInts, Ints[a], CmpBack); Inc(a); end; if ActIntsN > 0 then begin {Vybereme nejdříve končící interval} GetHeapMin(ActIntsN, ActInts, CmpBack, Tmp); if Tmp.e < i then begin {Už skončil?} CountCoord := False; Exit; end; T[Tmp.n][c] := i; end; end; CountCoord := True; end; {Vytiskne souřadnice věží} procedure Print; var i : Integer; begin WriteLn('Souradnice vezi jsou:'); for i := 1 to N do WriteLn(T[i][1], ' ', T[i][2]); end; begin ReadInp; {Načte vstup} if CountCoord(1) and CountCoord(2) then {Určí souřadnice věží - vešly se?} Print else WriteLn('Rozmisteni vezi neexistuje.'); end.

P-III-2 Nuly a jedničky

Nejprve ukážeme, že pro každé přirozené číslo N existuje přirozené číslo x, jehož ciframi jsou pouze číslice 0 a 1 a které je dělitelné číslem N. Označme x1=1, x2=11, x3=111 atd. Dále označme jako mi číslo xi mod N. Čísla mi mohou nabývat pouze hodnot od 0 do N-1 a proto alespoň dvě z čísel m1 až mN+1 musí být stejná - nechť např. mi=mj (i<j). Potom ale číslo xj-xi je dělitelné číslem N, neboť (xj-xi) mod N=mj-mi=0. Ciframi čísla xj-xi jsou zřejmě pouze číslice 0 a 1 a tedy číslo xj-xi splňuje podmínky ze zadání úlohy.

Nadále budeme uvažovat pouze ta čísla, jejichž dekadický zápis je tvořen pouze číslicemi 0 a 1. Předchůdcem čísla x nazveme číslo x div 10, tedy číslo x bez své poslední cifry; naopak následníky čísla x nazveme čísla 10x a 10x+1, tedy ta čísla, která lze vytvořit přidáním jedné cifry na konec čísla x. Číslo x budeme nazývat minimálním číslem pro zbytek z, jestliže x mod N=z, v dekadickém zápisu čísla x se vyskytují pouze číslice 0 a 1 a x je nejmenší číslo s těmito vlastnostmi. Nyní si dokážeme jednoduché lemma:

Lemma

Nechť x je minimální číslo pro zbytek z, nechť x' je předchůdcem x; označme z'=x' mod N. Potom x' je minimální číslo pro zbytek z'.

Důkaz

Postupujme sporem, tedy předpokládejme, že x' není minimální číslo pro zbytek z', tj. že existuje číslo x'' Toto lemma nám dává návod, jak počítat minimální čísla pro různé zbytky. Pro daný zbytek z lze spočítat minimální číslo x tak, že budeme postupně testovat v rostoucím pořadí následníky minimálních čísel pro ostatní zbytky a první následník y nějakého minimálního čísla, pro kterého platí y mod N=z je zřejmě hledané minimální číslo pro zbytek z.

Tímto postupem lze vygenerovat minimální čísla pro všechny zbytky, pro které existují: Položme l1=1 a pokud už známe l1,...,lk, položme lk+1 rovno nejmenšímu následníkovi některého z čísel l1,...,lk takovému, že lk+1 mod N je různý od všech li mod N pro 1<=i<=k. Z předchozích úvah ale vyplývá, že jednotlivá čísla li jsou minimální čísla pro zbytky zi=li mod N. Navíc podle prvního odstavce je jedno z čísel zi rovno nule.

Náš algoritmus bude pracovat přesně podle výše uvedeného popisu. V poli fronta si budeme pamatovat hodnoty zi a na m-té pozici v poli predchozi si budeme pamatovat zbytek předchůdce od minimálního čísla pro zbytek m - z hodnot v tomto poli jsme schopni jednoduše zkonstruovat minimální číslo pro zadaný zbytek. Postupně budeme brát hodnoty zi z pole fronta, spočítáme (10*zi) mod N a (10*zi+1) mod N a pokud jsme dosud nenašli číslo, jehož zbytek by byla jedna z těchto hodnot, tak tento zbytek přidáme na konec pole fronta a příslušně zmodifikujeme pole predchozi. Časová a paměťová složitost algoritmu je zřejmě O(N).

program nulajed; { P-III-2 } const MAXN=1000; var N:word; { zadané číslo N } predchozi:array[0..MAXN-1] of integer; { zbytek předchůdce minimálního čísla s daným zbytkem Hodnoty se zvláštním významem: -2 ... dosud nenalezeno minimální číslo pro tento zbytek -1 ... nemá předchůdce (číslo 1) } fronta:array[0..MAXN-1] of word; { fronta použitá pro generování minimálních čísel } ukazatel:word; { právě zpracovávaný prvek v poli fronta } vefronte:word; { počet prvků v poli fronta } procedure pridej(puvodni,novy:word); begin { přidá minimální prvek pro zbytek novy do fronty; jeho předchůdce je minimální pro zbytek puvodni } if predchozi[novy]<>-2 then exit; fronta[vefronte]:=novy; inc(vefronte); predchozi[novy]:=puvodni; end; procedure vypis(p:word); begin { vypíše číslo se zadaným zbytkem } if predchozi[p]>=0 then begin vypis(predchozi[p]); if (10*predchozi[p]) mod N=p then write(0) else write(1) end else write(1) end; begin readln(N); { načteme číslo N a inicializujeme pole predchozi } for ukazatel:=0 to N-1 do predchozi[ukazatel]:=-2; fronta[0]:=1 mod N; predchozi[fronta[0]]:=-1; ukazatel:=0; vefronte:=1; while (predchozi[0]=-2) do begin { generujeme čísla s různými zbytky... } pridej(fronta[ukazatel],(10*fronta[ukazatel]) mod N); pridej(fronta[ukazatel],(10*fronta[ukazatel]+1) mod N); inc(ukazatel); end; vypis(0); { vypíšeme výsledek a odřádkujeme } writeln end.

P-III-3 Dlaždice

Abychom nemuseli vše popisovat zbytečně složitě, zaveďme si jednoduché značení: Posloupnosti budou vždy složeny jen z nul a jedniček a všechny budou mít n prvků. Budeme je značit tučnými písmeny a jejich prvky písmeny s indexy, tedy například x je posloupnost obsahující prvky x1,...,xn. Počtu jedniček v posloupnosti x budeme říkat její váha a značit #x.

Posloupnost y je setříděním posloupnosti x právě tehdy, když platí současně následující dvě podmínky:

  1. y1 <= ... <= yn (je to neklesající posloupnost)
  2. #y=#x (x a y obsahují stejný počet jedniček a jelikož mají stejnou délku, tak i stejný počet nul, čili se navzájem liší pouze pořadím prvků)

Zabývejme se nejprve tím, jak ověřit druhou podmínku. Mohli bychom postupovat podobně, jako u příkladu v zadání oblastního kola: v každém řádku vydláždění odstranit po jedné jedničce z obou posloupností, a to opakovat tak dlouho, až obě posloupnosti budou obsahovat pouze nuly, což snadno ověříme barvou spodního okraje zdi. Tím úlohu vyřešíme s lineární složitostí, což ovšem, jak si ukážeme, není optimální. U myšlenky postupného "zjednodušování" testovaných posloupností však zůstaneme:

Tvrzení

#x=#y => #x mod 2 = #y mod 2 a #x'=#y', kde x' je posloupnost, která vznikne z posloupnosti x přepsáním každé druhé jedničky na nulu (to jest přepsáním první jedničky, ponecháním druhé, přepsáním třetí, ponecháním čtvrté atd.).

Důkaz

Pokud #x=#y, pak jistě #x mod 2 = #y mod 2, ale jelikož #x'=[#x/2] (v x' zbyla právě polovina jedniček z x, případná lichá jednička na konci byla odstraněna), musí platit i #x'=#y'. A naopak: pokud #x'=#y', mohou se posloupnosti x a y lišit pouze případnou lichou poslední jedničkou, což ovšem není možné, protože váhy #x a #y jsou buďto obě liché nebo obě sudé.

Vytvořme nejprve dlaždicový podprogram, který pro danou posloupnost x zadanou barvami horního okraje spočte x' na okraji dolním a #x mod 2 na okraji pravém (v tom smyslu, že vydláždění bude existovat právě tehdy, když barvy těchto okrajů splňují dané podmínky, a toto vydláždění bude mít jediný řádek), předpokládaje, že levý okraj má barvu 0. K tomu nám poslouží následující množina T0 typů dlaždic:
Nulajedničkové dlaždice pro okraj
Označíme-li si zi barvu pravé hrany a yi barvu dolní hrany i-té dlaždice vydlážděného řádku (z0 budiž barva levé hrany první dlaždice, tedy barva levého okraje zdi, což je 0), snadno ukážeme, že:

Zkombinujme nyní dva takové programy tak, aby pracovaly současně: jeden s posloupností x a druhý s y (posloupnosti jsou kódovány dvojicemi (xi,yi)), počítaly stejně kódované posloupnosti x' a y' a rovněž zbytky #x mod 2 a #y mod 2. K tomu nám stačí sestrojit množinu T1 obsahující "součiny" dvojic dlaždic z množiny T0, to znamená pro každé dvě dlaždice A a B z T0 na následujícím obrázku:
Dlaždice A a B
do T1 přidáme následující dlaždici:
Nová dlaždice pro dlaždice A a B
kde ae, bf, cg a dh jsou uspořádané dvojice barev. Existuje-li vydláždění řádku, který má na horní hraně dvojice (x1,y1),...,(xn,yn), na dolní hraně (x'1,y'1),...,(x'n, y'n), na levé (0,0) a na pravé (zx,zy), dlaždicemi typů z množiny T1, musí díky tomu, jak jsme si tyto typy nadefinovali, existovat i vydláždění řádku s horní hranou x1,...,xn, dolní x'1,...,x'n, levou 0 a pravou zx, jakož i řádku s horní hranou y1,...,yn, dolní y'1,... y'n, levou 0 a pravou zy dlaždicemi typů T0. A opačně -- existují-li tato dvě vydláždění, existuje i jejich složení sestavené z typů z množiny T1. Proto zx=#x mod 2, zy=#y mod 2 a spodní hrana opravdu obsahuje dvojice prvků posloupností x' a y'.

My ovšem potřebujeme akceptovat právě ta vydláždění, u nichž zx=zy, tedy s pravým okrajem jak (0,0), tak (1,1), ale máme k dispozici pouze jedinou barvu pravého okraje zdi. Proto rozšíříme množinu T1 na T2 tak, že ke každému typu dlaždice z T1 tvaru
Typ dlaždice z T_1
přidáme do T2 následující typ:
Nový typ dlaždice přidaný do T_2
kde P je barva pravého okraje, která se neshoduje s žádnou jinou barvou. Jelikož se tato dlaždice může vyskytnout výhradně těsně u pravého okraje (žádná dlaždice totiž nemá levou hranu barvy P, na kterou bychom mohli navázat), odpovídají korektní vydláždění pomocí této rozšířené sady dlaždic právě těm vydlážděním pomocí původní sady, u nichž je zx=zy.

Zbývá nám ještě přidat test vzestupnosti posloupnosti y, což vyřešíme přidáním dlaždic následujících typů:
Dlaždice pro testování vzestupnosti posloupnosti
kde 00, 01, 10 a 11 jsou barvy dvojic kódujících zadané posloupnosti x a y a 00, 01, 10 a 11 analogické kódy používané všemi ostatními dosud nadefinovanými dlaždicemi. Tím z T2 vznikne množina typů T, o které tvrdíme, že použita s barvou levého okraje 0, barvou pravého P a barvou dolního okraje 00, řeší zadanou úlohu se složitostí O(log n), což také ihned dokážeme:

Poznámka

Lepší hloubky než log n již není možno dosáhnout. To můžeme zdůvodnit podobně, jako jsme v předchozím kole dokazovali, že pro ověření symetrie posloupnosti potřebujeme hloubku minimálně lineární. Opět budeme počítat možná obarvení středního sloupce -- tentokráte si uvědomíme, že tato obarvení musí být rozdílná pro každé dva různé počty jedniček v x1,...,xn/2 -- pokud jsou jedničky pouze mezi těmito prvky a xn/2+1,...,xn jsou všechny nulové, musí setříděná posloupnost y obsahovat naopak ve své levé polovině samé nuly a v polovině pravé stejný počet jedniček, jako má x v polovině levé. Možných počtů jedniček mezi x1,...,xn/2 je n/2+1, možných obarvení středního sloupce <= bh, kde b je počet barev použitých v našem dlaždicovém programu (to je nějaká konstanta) a h je jeho složitost = výška středního sloupce. Z toho dostaneme:
bh >= n/2 + 1 > n/2
h > logb n - logb 2