Ř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
[x
1,y], [x
2,y+1], jistě platí, že x
1=x
2 nebo x
1+1=x
2. Pokud známe
součet x
1+x
2, dokážeme určit x
1a x
2: x
1=dolní celá
část((x
1+x
2)/2), x
2=horní celá část((x
1+x
2)/2). Proto můžeme
každou stranu, která není vodorovná, jednoznačně popsat
uspořádanou dvojicí čísel (i,j), kde i=x
1+x
2a j=y. Dvojici
(i,j) budeme nazývat souřadnicemi strany. Mějme stranu s se
souřadnicemi konců [x
1,y], [x
2,y+1] a stranu s' se souřadnicemi
konců [x
1',y], [x
2',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=(x
1'-x
1) +
(x
2'-x
2) (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=(x
1'+x
2')-(x
1+x
2), 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
- Část a vyřešíme po vyřešení části a.
- 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.
- 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
- 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.
- 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.