Matematická olympiáda – kategorie P

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

první soutěžní den 25.4.1996

P-III-1

 Uvažujme v naší souřadnicové soustavě vodorovný pás trojúhelníků, který je vymezen y-ovými souřadnicemi y a y+1. Jestliže vezmeme stranu mnohoúhelníka s procházející tímto pásem s koncovými body [x1,y], [x2,y+1], jistě platí, že x1=x2 nebo x1+1=x2. Pokud známe součet x1+x2, dokážeme určit x1a x2: x1=dolní celá část((x1+x2)/2), x2=horní celá část((x1+x2)/2). Proto můžeme každou stranu, která není vodorovná, jednoznačně popsat uspořádanou dvojicí čísel (i,j), kde i=x1+x2a j=y. Dvojici (i,j) budeme nazývat souřadnicemi strany. Mějme stranu s se souřadnicemi konců [x1,y], [x2,y+1] a stranu s' se souřadnicemi konců [x1',y], [x2',y+1], přičemž strana s je nalevo od strany s'. Potom část pásu ohraničená stranami s a s' je lichoběžník nebo v krajním případě trojúhelník a jeho obsah S=(x1'-x1) + (x2'-x2) (první sčítanec určuje počet jednotkových trojúhelníků, které mají jednu ze svých stran na spodní přímce pásu, druhý počet těch, které mají jednu ze stran na horní přímce pásu). Po úpravě dostaneme vztah S=(x1'+x2')-(x1+x2), což už je vyjádření přímo pomocí souřadnic stran.

Mějme nyní dva mnohoúhelníky A a B a zkoumejme průnik A, B a našeho vodorovného pásu. Tento průnik se bude zřejmě skládat z lichoběžníků (příp. trojúhelníků) ohraničených stranami mnohoúhelníků. Bod pásu patří do průniku, je-li nalevo od něj lichý počet stran A a zároveň lichý počet stran B. Tedy začátkem nějakého takovéhoto lichoběžníka bude strana, od níž vlevo je sudý počet stran jejího vlastního mnohoúhelníka a lichý počet stran druhého mnohoúhelníka. Naopak koncem takového lichoběžníka bude strana, od níž vlevo je lichý počet stran její vlastního a lichý počet stran druhého mnohoúhelníka. Strany mnohoúhelníků, které procházejí jedním pásem, můžeme setřídit zleva doprava, tj. podle jejich první souřadnice. Potom jediným průchodem přes utříděnou posloupnost stran jednoduše spočítáme plochu průniku.

Algoritmus je tedy následující: setřídíme strany obou mnohoúhelníků podle pásu, ve kterém se nacházejí (podle jejich druhé souřadnice), přičemž vodorovné strany můžeme vynechat. Strany téhož pásu setřídíme zleva doprava (podle první souřadnice). Potom procházíme zároveň oběma seznamy setříděných stran a hledáme strany, které jsou začátky nebo konci lichoběžníků, a jejich první souřadnice odpočítáváme nebo připočítáváme k celkovému součtu.

Zbývá ještě popsat realizaci třídění. Je třeba si uvědomit, že má-li mnohoúhelník nějaké dva vrcholy s x-ovými souřadnicemi i a j (i < j), má také vrcholy s x-ovými souřadnicemi i+1,i+2,...,j-1, neboť délka každé strany je 1. Rozdíl maximální a minimální x-ové souřadnice mnohoúhelníka je tedy nejvýše N. Totéž samozřejmě platí i pro y-ovou souřadnici. Proto na třídění stran použijeme algoritmus Radixsort. Strany setřídíme nejprve podle první souřadnice a potom podle druhé, přičemž v obou případech použijeme stabilní a lineární třídění. První souřadnice stran jsou ale součtem dvou souřadnic vrcholů, takže rozdíl dvou souřadnic stran může být i dvojnásobkem rozdílu souřadnic vrcholů.

Díky lineárnímu třídění je paměťová i časová složitost algoritmu O(N+M), kde N a M jsou počty stran mnohoúhelníků.

program Prunik_mnohouhelniku; const max=100; type pole=array[1..max+1,1..2] of integer; {v pole[i,1] je součet x1+x2, v pole[i,2] je y} var a,b,c:pole; {a,b-mnohoúhelníky, c-pom. pole} poc:array[0..2*max] of integer; {pom. pole při třídění} stran_a,stran_b:integer; {počet nevodorovných stran} plocha:integer; procedure nacti(var a:pole; var n:integer); var i,x1,y1,xs,ys,x,y,stran:integer; begin read(n); read(x1,y1); stran:=0; xs:=x1; ys:=y1; for i:=2 to n+1 do begin if i<=n then read(x,y) else begin x:=x1; y:=y1 end; if y<>ys then begin {vyloučí vodorovné strany} inc(stran); if y<ys then a[stran,2]:=y else a[stran,2]:=ys; a[stran,1]:=x+xs; end; xs:=x; ys:=y; end; n:=stran; end; procedure trid(var a:pole; n:integer); {radixsort} var i,j,co,min,max:integer; begin for co:=1 to 2 do begin min:=a[1,co]; max:=min; {najde minimum a maximum} for i:=2 to n do if a[i,co]<min then min:=a[i,co] else if a[i,co]>max then max:=a[i,co]; for i:=0 to max-min do poc[i]:=0; {vynuluje počty} for i:=1 to n do begin {do poc počet prvků dané hodnoty} j:=a[i,co]-min; inc(poc[j]); c[i]:=a[i]; {do c kopírujeme a} end; for i:=1 to max-min do {do poc[i] součet poc[0..i]} poc[i]:=poc[i]+poc[i-1]; for i:=n downto 1 do begin {přesun z c do a} j:=c[i,co]-min; a[poc[j]]:=c[i]; dec(poc[j]); end; {for i} end; {for co} end; procedure pocitej; var ai,bi,aj,bj,max:integer; begin if a[stran_a,2]>b[stran_b,2] then {zarážka} max:=a[stran_a,2]+1 else max:=b[stran_b,2]+1; a[stran_a+1,2]:=max; b[stran_b+1,2]:=max; ai:=1; bi:=1; aj:=0; bj:=0; while (ai<=stran_a) and (bi<=stran_b) do begin {porovnáme y-ové pásy} if a[ai,2]<b[bi,2] then begin {různá y} inc(ai); aj:=0; end else if b[bi,2]<a[ai,2] then begin inc(bi); bj:=0; end else begin {stejná y} if a[ai,1]<b[bi,1] then begin if bj mod 2=1 then {jsme uvnitř b} if aj mod 2=0 then plocha:=plocha-a[ai,1] {začáteční strana průniku} else plocha:=plocha+a[ai,1]; {koncová strana průniku} inc(ai); inc(aj); if a[ai,2]<>a[ai-1,2] then aj:=0; {nový řádek} end else begin {totéž pro b} if aj mod 2=1 then if bj mod 2=0 then plocha:=plocha-b[bi,1] else plocha:=plocha+b[bi,1]; inc(bi); inc(bj); if b[bi,2]<>b[bi-1,2] then bj:=0; end; end; end; end; begin nacti(a,stran_a); nacti(b,stran_b); plocha:=0; if (stran_a>0) and (stran_b>0) then begin trid(a,stran_a); trid(b,stran_b); pocitej; end; write(plocha); end.

P-III-2
  1. Část a vyřešíme po vyřešení části a.

  2. Protože 7 a N jsou nesoudělná čísla, existuje l takové, že 7l mod N = N-3 a 0<=l10 zjevně neplatí.

    Vkládejme do prázdného pole P procedurou Zarad postupně prvky (l+2)N, (l+1)N,...,4N, 3N, N. Uloží se postupně v tomto pořadí na místa 0,7,14,. ..,N-3. V poli je nyní obsazeno l+1 míst a tedy aspoň jedno místo je volné. Když nyní zavoláme proceduru Zarad s parametrem 2N, bude proměnná i postupně nabývat hodnot 0,7,14,. ..,N-3, neboť na pozicích 0,7,14,. ..,N-10 jsou uložena čísla větší než 2N. Ale P[i]=N a proto další hodnota indexu bude opět 0. Procedura bude proto cyklicky nabývat stále tyto hodnoty a tudíž není konečná pro každý vstup.

  1. Mějme funkci Posun, která nám vrátí další hodnotu, jakou by získal index i v proceduře Zarad (tato hodnota závisí na původní hodnotě i, na prvku x a prvku P[i]):
    function Posun(i:integer; x:integer):integer; begin if P[i]>x then posun:=(i+7) mod N else posun:=(i+3) mod N; end; V určitém stavu pole P chceme vyhledat prvek x. Definujme (nekonečnou) posloupnost indexů h0, h1, h2, ... , kde h0= x mod N a hi+1=Posun(hi,x).

    Mohou nastat tři případy:

    • Prvek x se v poli P nachází. Všimněte si, že procedura Zarad mění jen hodnoty nulových prvků pole P. Hodnoty na indexech, přes které přecházela procedura Zarad(x), se tedy nezměnily. Jsou to indexy h0, h1,... hk, kde k je nejmenší číslo takové, že P[hk]=x.
    • Prvek x se v poli nenachází a procedura Zarad by ho zařadila na volné místo P[i]. Při tomto zařazení by procedura prohlédla prvky P s indexy h0, h1,... hk, kde k je nejmenší číslo takové, že P[hk]=0 (resp. že i=hk).
    • Prvek x se v poli P nenachází a procedura Zarad pro vstup x neskončí. Také v tomto případě by procedura prohlédla indexy h0, h1,... Nechť k je nejmenší číslo takové, že existuje l < k takové, že h l=hk. Potom posloupnost {hn} začíná indexy h0, h1,... hl-1 a potom se už stále periodicky opakují indexy hl, hl+1,... hk-1.
    Funkce Vyhledej tedy rozpoznává tyto tři případy, v prvním případě vrátí hk a ve druhých dvou -1. V prvních dvou případech stačí postupně vypočítávat indexy hn, dokud nenajdeme 0 nebo x. Jestliže ale chceme zjistit, zda nenastal třetí případ, potřebujeme ověřit, jestli se právě vypočítaný index hn už předtím v posloupnosti nevyskytoval. Budeme se po poli posunovat se dvěma indexy i a j, každý bude postupně nabývat hodnot posloupnosti hn. Index i ale budeme posouvat "rychleji". Když i nabyde hodnoty hn, tak hodnota j bude h[n/2]. V případě, že se indexy v posloupnosti periodicky opakují, po jistém čase bude platit i=j. V okamžiku, kdy j nabyde poprvé hodnoty hl, i se nachází také někde v cyklu. Po každém posunu j se vzdálenost i a j zmenší o 1, neboť index i se mezitím posunul dvakrát a tak vlastně "dobíhá" index j. Proto se index j posune nejvýše k-krát a jelikož i se posouvá dvakrát tak často, celkový počet posunů je nejvýše 3k.

    function Vyhledej(x:integer); var i,j,vysledek:integer; menit_j:boolean; begin vysledek:=0; {výsledek ještě neznáme} i:=x mod N; {první index} j:=i; menit_j:=false; while vysledek=0 do {dokud neznáme výsledek} if P[i]=x then {našli jsme x} vysledek:=i else if P[i]=0 then {x v poli není} vysledek:=-1 else begin i:=posun(i,x); {posuneme i} if menit_j then begin {je-li třeba, posuneme j} j:=posun(j,x); if j=i then vysledek:=-1; {i a j se setkaly - cyklus} end; menit_j:=not menit_j; end; Vyhledej:=vysledek; end;

P-III-3
  1. Dokážeme sporem, že není možné sestrojit požadovaný D0L systém. Nechť tedy existuje D0L systém s růstovou funkcí n2. Nechť má tento D0L systém pouze jedno pravidlo. Potom toto pravidlo musí mít tvar a->ai a w1=a, neboť |w1|=f(1)=1. Pro w2 platí w2=ai a |w2|=f(2)=4. Z toho vyplývá, že i=4. Ale pak pro w3 platí w3=a^(i2) a |w3|=f(3)=9. Dostáváme tedy, že 9=i2=42=16, což je spor.

    Náš D0L systém musí tedy mít alespoň dvě pravidla. Nechť jsou to pravidla a->u, b->v, kde u,v jsou z {a,b}*. Bez újmy na obecnosti můžeme předpokládat, že w1=a. Potom w2=u a tudíž |u|=f(2)=4. Nechť slovo u obsahuje k znaků a. Potom w3=ukv4-k a platí, že |w3|=f(3)=9. Ale současně platí |w3|=k|u|+(4-k)|v| a |u|=4. Dostáváme tedy rovnici 4k+4|v|-k|v|=9. Jestliže za k postupně dosadíme všechny možné hodnoty (0,1,2,3,4), dostáváme pro |v| následující rovnosti: 4|v|=9, 4+4|v|-|v|=9, 8+4|v|-2|v|=9, 12+4|v|-3|v|=9 a 16+4|v|-4|v|=9. Ani jedna z těchto rovností však nemá nezáporné celočíselné řešení, a proto D0L systém s požadovanými vlastnostmi neexistuje.

  2. D0L systém s požadovanými vlastnostmi neexistuje. Dokážeme to opět sporem. Nechť tedy existuje D0L systém s k-prvkovou abecedou a růstovou funkcí f(n)=[logk+1(n+1)]+1.

    Nechť m>1. Označme n1 nejmenší takové číslo n, pro které f(n)=m, a n2 největší takovéto číslo. Potom n1=(k+1)m-1-1 a n2=(k+1)m-2. Tedy všechna slova w s indexem n1, w s indexem n1+1, ..., w s indexem n2 mají délku m. Jejich počet je n2-n1+1 = k(k+1)m-1. Ale různých slov délky m je km a km < k(k+1)m-1. Proto určitě existují čísla i,l>0 taková, že wi=wi+l. Když ale ze slova wi vznikne po l krocích opět wi, úsek wi,wi+1,... wl-1 se bude i dále stále periodicky opakovat. Tedy D0L systém vyprodukuje nekonečně mnoho slov délky m, což je spor, neboť takových slov má být n2-n1+1.