Řešení úloh oblastního kola 45. ročníku
sobota 27.1.1996
P-II-1
Uvažujme v naší soustavě souřadnic pás trojúhelníků, který je
vymezen x-ovými souřadnicemi x a x+1. Vezmeme průnik tohoto pásu
s hranicí našeho n-úhelníka. Každé hraně n-úhelníka uvnitř pásu
přiřadíme směr podle toho, v jakém pořadí byly zadány její krajní
body. Dostaneme tak soustavu hran jednotkové délky, přičemž:
- Počet hran je sudý (pokud projdeme přes tento pás doprava,
potom abychom n-úhelník uzavřeli, musíme přes tento pás přejít
také doleva a naopak).
- Je-li směr některé hrany doleva, směr nejbližší nižší a vyšší
hrany je doprava a naopak.
- Nejvyšší a nejnižší hrana vede ve všech pásech (tzn. pro
všechna x) stejným směrem, přičemž nejvyšší hrana vede opačným
směrem než nejnižší hrana.
Plocha průniku pásu a našeho n-úhelníka je zřejmě rovna součtu
ploch ohraničených nejvyšší hranou a druhou nejvyšší hranou,
třetí a čtvrtou nejvyšší hranou, ... , druhou a první nejnižší
hranou. Předpokládejme nyní, že nejnižší hrana vede doleva. Potom
plochu průniku n-úhelníka a našeho pásu spočítáme tak, že plochu
v pásu "pod" hranou vedoucí doprava vždy přičítáme a plochu "pod"
hranou vedoucí doleva odčítáme.
Toto však nemusíme provádět po jednotlivých pásech. Nejprve
položíme plocha:=0. Nechť y je výška aktuálního bodu n-úhelníka.
Jestliže další bod leží napravo dole (relativní souřadnice
(1,-1)), připočítáme k ploše 2y-1, pokud je napravo (relativní
souřadnice (1,0)), přičteme 2y. Jestliže je další bod nalevo
nahoru (relativní souřadnice (-1,1)), odečteme od plochy 2y+1,
pokud je nalevo (relativní souřadnice (-1,0)), odečteme 2y.
V ostatních případech (relativní souřadnice (0,1) a (0,-1))
nepřipočítáváme nic, neboť tyto hrany neprotínají žádný pás.
Co se stane, jestliže byla orientace hran opačná, než jsme
předpokládali? Potom dostaneme záporné číslo a jeho absolutní
hodnota je rovna ploše n-úhelníka.
Poznámka: V předcházející úvaze jsme předpokládali, že se celý
n-úhelník nachází jen nad osou x. Je však jasné, že algoritmus
zůstává beze změny, i když bude n-úhelník ležet celý nebo
částečně pod osou x.
Správnost algoritmu je zřejmá z předcházejících úvah. Časová
složitost algoritmu je O(n), paměťová O(1).
program sit;
var n,xs,ys,x0,y0,xn,yn,x,y,plocha,i:integer;
begin
readln(n); {počet bodů}
readln(xs,ys); {první bod}
x0:=xs;y0:=ys; {uschovat první bod}
plocha:=0;
for i:=1 to n do begin
if i=n then begin xn:=x0;yn:=y0 end {zakončit n-úhelník}
else readln(xn,yn); {načíst další bod}
x:=xn-xs;y:=yn-ys; {x,y jsou relativní souř.}
case x of
-1: plocha:=plocha-2*ys-y; {vlevo -> odčítat}
1: plocha:=plocha+2*ys+y; {vpravo -> přičítat}
end;
xs:=xn;ys:=yn;
end;
writeln(abs(plocha));
end.
P-II-2
- Označme h(x):=(x mod 10 + x div 10) mod N. Funkce Vyhledej při
hledání prvku x postupně prohlíží prvky pole P s indexy h(x),
(h(x)+7) mod N, (h(x)+14) mod N,... ,(h(x)+7l) mod N. Skončí,
když nastane jedna z těchto tří možností:
- najde hledaný prvek x
- najde prvek menší než x
- najde prázdné políčko (prvek s hodnotou 0)
Pokud nastala první možnost, prvek se v poli nachází, jinak
v poli není. N a 7 jsou nesoudělná čísla. Z toho vyplývá, že pro
každé i {0,1,...,N-1} existuje j {0,1,...,N-1} takové, že
i=(h(x)+7j) mod N. V poli je aspoň jedno prázdné políčko (M
Nechť se v poli P prvek x nachází na místě s indexem i. Nechť
j {0,1,...,N-1} je takové číslo, že i=(h(x)+7j) mod N. Aby funkce
Vyhledej prvek x našla, musí platit, že prvky s indexy h(x),
(h(x)+7) mod N, (h(x)+14) mod N,... ,(h(x)+7(j-1)) mod N budou
větší než x.
- Pokud do tabulky chceme uložit prvek x, postupujeme opět po
posloupnosti indexů h(x), (h(x)+7) mod N, (h(x)+14) mod N,...,
(h(x)+7l) mod N tak dlouho, až najdeme prvek menší než x nebo
prázdné políčko. Jestliže jsme našli prázdné políčko, prvek x tam
můžeme uložit a funkce Vyhledej ho jistě najde, neboť před ním
bude prohledávat jen větší prvky. Pokud však je na tomto místě
prvek s hodnotou y1 (y1 < x), uložíme sem prvek x. Při hledání
prvku y1 se předtím funkce Vyhledej zastavila na indexu
(h(x)+7l) mod N, ale tam je nyní prvek x větší než y1, takže
funkce bude pokračovat dále po indexech (h(x)+7 (l+1)) mod N,...,
(h(x)+7 l1) mod N. Prvek y1 uložíme na místo (h(x)+7 l1) mod N.
Jestliže tam předtím bylo prázdné políčko, skončíme, jestliže tam
byl prvek y2 (y2 < y1), opět postupujeme dále po indexech
(h(x)+7 (l1+1)) mod N,..., (h(x)+7l2) mod N. Toto opakujeme,
dokud nenajdeme prvok yk, který se již uloží na prázdné políčko.
Na základě tohoto postupu můžeme sestavit proceduru Zarad:
procedure Zarad(X:integer);
var i:integer;
begin
i:=(X mod 10 + X div 10) mod N; {i:=h(X)}
while P[i]<>0 do begin
if P[i] < X then {našli jsme menší prvek}
swap(P[i],X); {vymění hodnoty P[i] a X}
i:=(i+7) mod N; {posuneme se dále}
end;
P[i]:=X; {na volné políčko uložíme X}
end;
Procedura Zarad vždy skončí, neboť M
- Prvek y se v poli P nenachází. Funkce Vyhledej(y) nemůže nalézt
něco, co v poli P není, a proto vrátí správný výsledek.
- y=x. V tomto případě už z popisu algoritmu vyplývá, že funkce
Vyhledej prvek x najde.
- y<>x, y se nachází v poli P a jeho poloha se během výpočtu
procedury Zarad(x) nezměnila. Předtím funkce Vyhledej
prohledávala indexy h(y), (h(y)+7) mod N,..., (h(y)+7l) mod N. To
znamená, že pro každé i, 0 <= i < l platilo P[(h(y)+7i) mod N]
> y. Protože se hodnota žádného prvku z P během provádění
Zarad(x) nesnížila, platí to i nadále a proto Vyhledej(y) bude
prohledávat stejné indexy a úspěšně y najde.
- y<>x, y se nachází v poli P a jeho poloha se během výpočtu
procedury Zarad(x) změnila, t.j. je to jeden z prvků y1, y2,...,
yk. Nechť předtím Vyhledej prohledávala indexy h(y), (h(y)+7) mod
N,..., (h(y)+7l) mod N. Ze stejných důvodů jako v předcházejícím
případě ani nyní neskončí dříve, ale na místě s indexem
(h(y)+7l) mod N je nyní prvek větší než y, a proto funkce bude
pokračovat dále. Z popisu algoritmu však vyplývá, že prvek, na
kterém se prohledávání zastaví, je právě hledaný prvek y.
P-II-3
Celkový posun pera je součtem jednotlivých vektorů určených
vstupní posloupností. Když starší kreslicí zařízení udělá pohyb
o jednotku delší nebo kratší, je to to totéž, jako kdyby se kromě
určeného vektoru posunulo ještě o jednotkový vektor ve směru nebo
proti směru svého natočení. Protože sčítání vektorů je
komutativní, představme si, že se tyto posuny o jednotkové
vektory provedou všechny až nakonec. Nechť množina A je množina
obsahující ke každému vektoru ze vstupní posloupnosti dva
navzájem opačné jednotkové vektory (ve směru a proti směru tohoto
vektoru). Naší úlohou tedy je vybrat z množiny A podmnožinu,
jejíž součet je co nejdelší. Vybraná podmnožina může být
libovolná (zařízení se sice vždy posune nejvýše o jeden z dvojice
navzájem opačných vektorů, ale pokud bychom vybrali oba, je to
totéž, jako kdybychom nevybrali ani jeden z nich).
Podmnožina s největším součtem jistě obsahuje z každé dvojice
opačných vektorů právě jeden. To lehce dokážeme sporem: nechť
vektor (x,y) je součtem podmnožiny s největším součtem, která
neobsahuje ani jeden z jednotkových vektorů (x1,y1) a (-x1,-y1).
Potom ale jeden z vektorů (x+x1,y+y1), (x-x1,y-y1) je určitě
delší než vektor (x,y). Platí, že x12+y12=1 a jedno z čísel 1 +
2(x x1 + y y1),
1 - 2(x x1 + y y1) je určitě kladné. Délka
vektoru (x+x1, y+y1)
je sqrt(x2 + y2 + x12 +
y12 + 2(x x1 +
y y1)) a délka vektoru (x-x1,
y-y1) je
sqrt(x2 + y2 + x12 +
y12- 2(x x1 + y y1)).
Jedna z těchto délek je tedy jistě větší než
délka vektoru (x,y), která
je rovna sqrt(x2 + y2). Proto vektor
(x,y) není vektor s největší možnou délkou. Podobně se dá
zdůvodnit, že pokud A obsahuje více stejných dvojic vektorů, do
podmnožiny s největším součtem se vybere z každé dvojice stejný
vektor.
Nyní dokážeme následující větu: Hledané řešení obsahuje všechny
vektory z A ležící v jedné polorovině určené některou přímkou
vedoucí bodem (0,0). Jsou-li některé dvojice vektorů rovnoběžné
s přímkou, vyberou se vektory v jednom směru.
Důkaz: Nechť (x,y) je součet podmnožiny s nejdelším součtem,
nechť přímka p je kolmá na (x,y) a prochází bodem (0,0). Nechť
(x1,y1) je libovolný vektor
z poloroviny, v níž se nachází
(x,y). Potom úhel vektorů (x1,y1) a
(x,y) je nejvýše 90 stupňů.
Proto délka vektoru (x+x1,y+y1)
je větší než délka (x,y) (podle
kosinové věty). Pokud by naše podmnožina neobsahovala některý
z vektorů z této poloroviny, její součet se přidáním tohoto
vektoru tudíž prodlouží, takže by nemohla být hledaným řešením.
Jestliže by naopak obsahovala některý vektor z opačné poloroviny,
jeho ubrání je totéž jako přidání vektoru k němu opačného (který
je už z naší poloroviny), a to opět prodlouží součet.
Nechť a1, a2,..., a2n
jsou jednotkové vektory z množiny
A uspořádané podle směru (vektor ai+n
je opačný k vektoru ai pro
1<=i<=n). Vezměme dva sousední vektory z takto setříděné
posloupnosti. Poloroviny určené všemi přímkami procházejícími
"mezi" těmito dvěma vektory obsahují stejnou podmnožinu vektorů
z A, a proto stačí uvažovat jen přímky se směry vektorů z A.
Polorovina určená přímkou ve směru vektoru ai obsahuje
vektory
ai, ai+1,..., ai+n-1,
1<=i<=n. Stačí tedy určit všechny takovéto
součty a vybrat z nich největší. To lze provést pro již
setříděnou posloupnost vektorů v čase O(n).
Vzhledem k tomu, že směry vektorů určených vstupní posloupností
jsou celé čísla od 0 do 359, můžeme je uspořádat v čase O(n)
přihrádkovým tříděním, t.j. pro každý ze směrů spočítáme, kolik
vektorů je v tomto směru. Máme-li l jednotkových vektorů téhož
směru, můžeme je považovat za jeden vektor délky l. Stačí dokonce
použít jen pole od 0 do 179, neboť vektor se směrem j a vektor
k němu opačný se směrem j+180o mají stejnou délku.
program kreslici_zarizeni;
var a:array[0..359] of integer;
{součet délek vektorů v jednotlivých směrech}
i:integer;
d,maxd:real; {aktuální a maximální vzdálenost}
x,y:real; {aktuální součet}
uhel:integer; {aktualní úhel}
s:string; {vstupní řetězec}
us:integer; {ukazatel aktuálního znaku v řetězci}
procedure CtiCislo(var n:integer);
var u1,err:integer;
begin
while not(s[us] in ['-','0'..'9']) do inc(us);
u1:=us;inc(us);
while s[us] in ['0'..'9'] do inc(us);
val(copy(s,u1,us-u1),n,err);
end;
procedure Posloupnost;
var x,i,sus:integer;
begin
{us ukazuje na '['} inc(us);
while s[us]<>']' do begin
CtiCislo(x);
if s[us]='[' then begin
{x krát opakujeme následující posloupnost}
sus:=us;
for i:=1 to x do begin
us:=sus;
Posloupnost;
end;
end
else begin
CtiCislo(x); {úhel}
inc(a[uhel]);
inc(a[(uhel+180)mod 360]); {přidáme i opačný úhel}
uhel:=(uhel+x) mod 360;
end;
end;
{us ukazuje na ']'} inc(us);
end;
procedure Nacti;
var i:integer;
begin
for i:=0 to 359 do
a[i]:=0;
readln(s); {načtení řetězce}
uhel:=0; {počáteční úhel}
us:=1; {nastavení ukazatele do pole s}
Posloupnost; {rozkódování vstupní posloupnosti}
end;
procedure Pridej(i:integer);
begin
{posune x,y o vektor délky a[i] směrem i}
x:=x+(a[i]*cos(i/180*pi));
y:=y+(a[i]*sin(i/180*pi));
end;
begin
Nacti;
x:=0; y:=0;
for i:=0 to 179 do
Pridej(i); {součet první poloroviny}
maxd:=sqr(x)+sqr(y);
for i:=180 to 359 do begin
Pridej(i); {uber vektor i-180}
Pridej(i); {přidej vektor i}
d:=sqr(x)+sqr(y); {čtverec vzdálenosti (x,y) od (0,0)}
if d>maxd then
maxd:=d;
end;
writeln('Pero mohlo skončit nejvýše ',sqrt(maxd):0:2,
' od požadovaného místa');
end.
P-II-4
- Dokážeme sporem, že není možné sestrojit požadovaný D0L
systém. Nechť existuje D0L systém s růstovou funkcí nn. Vezmeme
k rovné maximální hodnotě z délek pravých stran pravidel. Z toho
vyplývá, že máme-li v i-tém kroku slovo délky ii, v i+1-ním kroku
může náš D0L systém vygenerovat slovo délky nejvýše k ii.
Uvažujme nyní slovo wk. Jeho délka je kk.
Pro délku slova wk+1
potom musí platit:
|wk+1| <
k|wk| = k kk =
kk+1 < (k+1)k+1
což je spor, neboť délka slova wk+1 má být (k+1)k+1.
- Řešením je D0L systém
({b,c,d},{b->b2,c->b2c2,
d->b2c4d2},dd).
Tvrzení: V n-tém kroku je tvar slova
(b(n-1)^2c2(n-1)d)2^n
a tedy f(n)=2n((n-1)2+2(n-1)+1)=2nn2.
Důkaz: Pro n=1 tvrzení zřejmě platí.
Nechť dále wn=
b2^n (n-1)^2}
c2^n 2(n-1) d2^n. Potom po uplatnění
pravidel bude
wn+1=
(b(n-1)^2b2(n+1)c2(n-1)bc2d =
bn^2c2nd)2^(n+1),
čímž je tvrzení dokázáno.