Matematická olympiáda – kategorie P

Řešení úloh domácího kola 45. ročníku

P-I-1

První část hodnoťte celkem 4 body rozdělenými mezi funkčnost programu (3 body) a popis (1 bod). Popis by měl matematicky zdůvodňovat vztahy použité při konstrukci programu.

Druhou část hodnoťte 6 body rozdělenými mezi funkčnost programu (3 body), efektivitu (2 body) a popis (1 bod). V případě složitosti (paměťové nebo časové) větší než O(N) strhněte body za efektivitu. Body za popis přiznávejte jen v případě, že popis obsahuje zdůvodnění správnosti a odhad složitosti.

Úlohu je možné řešit i s konstantní pamětí, toto řešení je však poměrně nepřehledné, neboť je třeba sloučit část a a b do jedné procedury.

Nejprve si ukážeme, jak lze přepočítat zadané souřadnice do pravoúhlé souřadnicové soustavy. Označme (tx,ty) souřadnice v naší trojúhelníkové soustavě a (kx,ky) souřadnice v pravoúhlé souřadnicové soustavě.
Nákres trojúhelníkové souřadné soustavy
Z vlastností pravoúhlého trojúhelníka na obrázku vyplývá:
ky/ty = cos 30o
(kx-tx)/ty = sin 30o
a tedy pro souřadnice (kx,ky) platí:
ky = sqrt(3)/2 ty
kx = 1/2 ty+tx
Pro účely přepočítání na souřadnice na obrazovce zavedeme následující proměnné: zvětšení k (počet pixelů na obrazovce na jednotku délky) souřadnice počátku souřadnicové soustavy na obrazovce (ox,oy) Ve vzorovém řešení je k konstanta a ox, oy se počítají tak, aby bod (0,0) ležel ve středu obrazovky.

Shrneme výsledky předcházejících úvah. Bod zadaný v pravoúhlé soustavě souřadnicemi (kx,ky) se zobrazí na obrazovce na souřadnice (ox+k kx,oy-k ky). Je-li bod zadán v trojúhelníkové soustavě souřadnicemi (tx,ty), potom jeho souřadnice v pravoúhlé soustavě jsou
ky = (sqrt{3})/2 ty
kx = 1/2 ty+tx
a na obrazovce se tedy zobrazí na souřadnice (ox+k tx+k 1/2 ty, oy-k sqrt(3)/2 ty). Jestliže nyní označíme jxx:=k, jyx:=1/2 k,jyy:=- sqrt(3)/2 k dostáváme, že se bod se souřadnicemi (tx, ty) v trojúhelníkové soustavě zobrazí na obrazovce do bodu (ox+jxxtx+jyxty, oy+jyyty).

Jelikož všechny vrcholy našeho N-úhelníka musí ležet v mřížových bodech a vzdálenost následujícího vrcholu musí být vždy 1 od předcházejícího, přicházejí pro vrchol se souřadnicemi (tx,ty) v úvahu tyto vrcholy jako následující (odpovídající směry, v nichž vrcholy leží vzhledem k (tx,ty) označme od 0 po 5 v pořadí, v jakém jsou zde vypsány): (tx,ty+1), (tx+1,ty), (tx+1,ty-1), (tx,ty-1), (tx-1,ty), (tx-1,ty+1).

Nechť jsme nyní do vrcholu (tx,ty) přišli ze směru ss a odcházíme z něho ve směru sn. Vidíme, že pokud sn=ss, potom jsme se v bodě neotočili, pokud sn=(ss+1) mod 6 nebo sn=(ss+2) mod 6 potom jsme se otočili doprava, jinak doleva (případ sn=(ss+3) mod 6 nemůže nastat).

Budeme obcházet náš N-úhelník po obvodu (tzn. v pořadí, v jakém byly zadány jeho vrcholy - připomeňme si, že pořadí bodů může být zadáno buď ve směru, nebo proti směru hodinových ručiček) a budeme sledovat, v jakém směru se otáčíme v jednotlivých vrcholech (směr otáčení je dán menším z dvou úhlů u vrcholu). Je-li náš N-úhelník konvexní, potom se zřejmě musíme otáčet stále stejným směrem a naopak, jestliže konvexní není, musíme se během obcházení otočit aspoň jednou doprava a aspoň jednou doleva.

Tato jednoduchá úvaha bude základem našeho algoritmu. Obcházíme postupně N-úhelník, přičemž když se otočíme doprava, nastavíme proměnnou doprava, když se otočíme doleva, nastavíme proměnnou doleva. Jestliže jsou na konci obě proměnné nastavené, N-úhelník není konvexní, v opačném případě je konvexní.

Časová i paměťová složitost tohoto algoritmu je lineární (O(N)), správnost vyplývá z výše uvedené úvahy.

program sit; uses Graph; const k=30; {zvětšení} maxn=1000; {max.počet vrcholů} var x,y:array [1..maxn] of integer; {souřadnice vrcholů mnohoúhelníka} n:integer; {počet vrcholů} ox,oy:integer; {začátek souř. soustavy na obrazovce} jxx:real; {delka jednotkoveho vektoru osy x} jyx,jyy:real; {delka jednotkoveho vektoru osy y} inp:text; {vstupni soubor} procedure Nacitej; var i:integer; begin readln(inp,n); {počet vrcholů} for i:=1 to n do begin readln(inp,x[i],y[i]); {souřadnice i-tého vrcholu} end; end; procedure Inicializace; var grDriver:integer; grMode:integer; maxx,maxy,minx,miny:real; {hranice n-úhelníka} kx,ky:real; {koeficienty zvětšení} i:integer; begin grDriver := Detect; InitGraph(grDriver,grMode,''); {Vypočítáme střed souřadnicové soustavy na obrazovce} ox:=GetMaxX div 2; oy:=GetMaxY div 2; {Vypočítáme jxx,jyx,jyy} jxx:=k; jyx:=k/2; jyy:=-sqrt(3)*k/2; end; procedure Kresli; var sx,sy,nx,ny:integer; i:integer; s:string; begin sx:=round(ox+x[1]*jxx+y[1]*jyx); sy:=round(oy+y[1]*jyy); for i:=2 to n do begin circle(sx,sy,3); str(i-1,s); outtextxy(sx+4,sy+4,s); nx:=round(ox+x[i]*jxx+y[i]*jyx); ny:=round(oy+y[i]*jyy); line(sx,sy,nx,ny); sx:=nx;sy:=ny; end; circle(sx,sy,3); str(n,s); outtextxy(sx+4,sy+4,s); nx:=round(ox+x[1]*jxx+y[1]*jyx); ny:=round(oy+y[1]*jyy); line(sx,sy,nx,ny); end; function JeKonvexni:boolean; const smery:array [-1..1,-1..1] of integer= ((-1,4,5), (3,-1,0), (2,1,-1)); var i:integer; levy,pravy:boolean; ssmer,nsmer:integer; begin levy:=false;pravy:=false; ssmer:=smery[x[1]-x[n],y[1]-y[n]]; for i:=2 to n do begin nsmer:=smery[x[i]-x[i-1],y[i]-y[i-1]]; if nsmer > ssmer then ssmer:=ssmer+6; case ssmer-nsmer of 1,2:levy:=true; 4,5:pravy:=true; end; ssmer:=nsmer; end; nsmer:=smery[x[1]-x[n],y[1]-y[n]]; if nsmer > ssmer then ssmer:=ssmer+6; case ssmer-nsmer of 1,2:levy:=true; 4,5:pravy:=true; end; JeKonvexni:=levy xor pravy; end; begin assign(inp,'p11.in'); reset(inp); while not(eof(inp)) do begin Nacitej; {část a} Inicializace; Kresli; readln; closegraph; {část b} write('N-úhelník '); if not(JeKonvexni) then writeln('není konvexní') else writeln('je konvexní'); readln; end; close(inp); end.

P-I-2

Body rozdělte takto: pochopení práce s datovou strukturou - 2 body; správnost algoritmu - 3 body; efektivita algoritmu - 3 body; popis algoritmu - 2 body.

Body za pochopení práce s datovou strukturou udělte i tehdy, je-li algoritmus nesprávný, ale z popisu je zřejmé, že řešitel umí pracovat s uvedenou datovou strukturou. U efektivity strhněte 1 bod v případě, že algoritmus je lineární, ale nároky na paměť nejsou konstantní, u algoritmů s časovou složitostí horší než lineární strhněte 2 a více bodů. V popisu algoritmu by neměl chybět odhad časové a paměťové složitosti a také úvahy, které potvrzují správnost algoritmu.

Má-li existovat posloupnost hodnot H[1], ..., H[L], musí především platit, že L < N. Dále platí, že když do pole zařazujeme i-tou hodnotu, počet kolizí K[i] je nejvýše i-1. (K[i]=i-1 tehdy, pokud dojde ke kolizi se všemi už zařazenými prvky). Z toho ale vyplývá, že jestliže CK > 0+1+ ... + (L-1) = L(L-1)/2, posloupnost opět neexistuje.

Označme a # b := (a+7b) mod N. Vezmeme nyní libovolný index nějakého prvku v našem poli j. Potom jestliže procházíme prvky j # 1, j # 2, ..., j # N, přejdeme každým prvkem našeho pole právě jednou (protože N je prvočíslo).

Máme-li v poli obsazeno k prvků s indexy j0, j0 # 1, j0 # 2, ... , j0 # (k-1), pak pro libovolné K[k+1], kde K[k+1] je číslo od 0 do k, umíme nalézt vhodný prvek H[k+1] takový, že se zařadí do pole na index j0 # k. Označme si ik+1:=(H[k+1] div 10 + H[k+1] mod 10) mod N (viz procedura Zarad) první index vypočítaný pro prvek H[k+1] v proceduře Zarad. Potom když vezmeme
ik+1=j0 # (k-K[k+1])
tak se nám prvek H[k+1] zařadí na pozici j0 # k.

Pro libovolný počáteční index j0 a posloupnost K (K[i] <= i-1 pro i=1,2,...,L) tedy umíme tímto způsobem nalézt příslušnou posloupnost prvních indexů j0=i1,i2 ,... ,iL.

Posloupnost K však není zadána, známe jen její součet CK. Proto si ji můžeme zvolit libovolně, pokud možno co nejjednodušším způsobem. Položme například K[i]:=i-1 pro i=1,2,... ,m a jestliže m <> L K[m+1]:=CK- m(m-1)/2 a K[i]:=0 pro i=m+2,... ,L, přičemž m vezmeme největší takové, že m(m-1)/2 <= CK. Řešením kvadratické rovnice lehce zjistíme, že m=[(1+sqrt(1+8CK))/2]. Dále je třeba vyřešit problém, jak zvolit j0 tak, aby se při výše popsané volbě posloupnosti K první index posledního prvku posloupnosti H nalezený pomocí vztahu iL=j0 # (L-1-K[L]) skutečně rovnal hodnotě vypočítané v proceduře Zarad ((H[L] div 10 + H[L] mod 10) mod N). Pro operaci # platí a mod N = (a # b) # (-b) a tedy pokud iL=j0 # (L-1-K[L]), potom j0=i0 # (-(L-1-K[L])).

Zbývá určit, jak z hodnoty prvního indexu ij vypočítat hodnotu prvku posloupnosti H[j]. Je zřejmé, že bude-li mít prvek hodnotu 10ij, určitě bude jeho index ij. Prvky posloupnosti H však mají být nenulové a navzájem různé. Proto k j-tému prvku ještě připočítáme číslo jN. Kdyby se takto vypočítaná hodnota náhodou rovnala číslu G, odečteme od něj číslo 9 (tím bude H[j] mod 10 = 1, ale hodnota H[j] div klesne o 1, takže součet se zachová).

Shrňme předcházející úvahy do funkce prvok(i,j), která pro daný první index i a pořadové číslo j určí hodnotu H[j].

Funkce prvok (i,j)

Na závěr uveďme přehledný zápis celého algoritmu tak, jak byl popsán výše:

Časová složitost algoritmu je lineární (O(N)), paměťová konstantní (O(1)), neboť hodnoty K[i] můžeme přímo vypisovat.

P-I-3

Body rozdělte mezi funkčnost programu (8 bodů) a popis programu (2 body). V hodnocení nedělejte rozdíly mezi programy, které používají rekurzivní volání, a programy, které používají pro tento účel vlastní zásobník. Rovněž není třeba klást důraz na způsob, jakým byl načtený řetězec rozložen na jednotlivé části.

Řešení neobsahuje prakticky žádné vážnější problémy, proto se v tomto případě omezíme jen na popis samotného programu.

Jádrem programu je procedura Zarizeni. Tato procedura slouží k přečtení a vykonání vstupní posloupnosti z řetězce s od indexu us, přičemž se předpokládá, že s[us]='['. Hlavní program zavolá na začátku tuto proceduru, a je-li součástí posloupnosti další posloupnost, zavolá se tato procedura rekurzivně odpovídající počet krát.

Další pomocné procedury jsou: procedura Inicializace, která slouží k inicializaci grafické stránky a proměnných. Procedura CtiCislo čte ze vstupního řetězce s nejbližší číslo od indexu us a procedura KresliCaru převede polární souřadnice na kartézské a vykreslí odpovídající čáru.

Všimněte si, že v případě inicializace úhlu na začátku na 0o bychom v proceduře KresliCaru zaměnili funkce cos a sin.

program Kreslici_zarizeni; uses graph; var uhel:integer; {aktuální úhel} s:string; {vstupní řetězec} us:integer; {ukazatel aktuálního znaku v řetězci} inp:text; {vstupní subor} procedure KresliCaru(uhel,x:integer); var relx,rely:integer; begin relx:=round(x*cos(uhel/180*pi)); rely:=round(x*sin(uhel/180*pi)); LineRel(relx,rely); end; procedure CtiCislo(var n:integer); var u1,err:integer; begin {vymezíme si, ve které části řetězce se nachází čtené číslo (s[u1..us-1])} while not(s[us] in ['-','0'..'9']) do inc(us); u1:=us;inc(us); while s[us] in ['0'..'9'] do inc(us); {přepočítáme na číslo} val(copy(s,u1,us-u1),n,err); end; procedure Zarizeni; var x,i,alpha:integer; sus:integer; {slouží k zapamatování pozice us} begin {us ukazuje na '['} inc(us); while s[us] <> ']' do begin CtiCislo(x); if s[us]='[' then begin {x*opakujeme násl. seznam} sus:=us; for i:=1 to x do begin us:=sus; Zarizeni; end; end else begin {Přesouváme sa o délku x a otáčíme o úhel alpha} CtiCislo(alpha); KresliCaru(uhel,x); uhel:=uhel+alpha; end; end; {us ukazuje na ']'} inc(us); end; procedure Inicializace; var grDriver : Integer; grMode : Integer; begin grDriver := Detect; InitGraph(grDriver,grMode,''); uhel:=270; {počáteční úhel} MoveTo(GetMaxX div 2,GetMaxY div 2); {nastavení počáteční polohy} us:=1; {nastavení ukazatele do pole s} end; begin assign(inp,'p13.in'); reset(inp); while not(eof(inp)) do begin Inicializace; readln(inp,s); {načtení řetězce} Zarizeni; readln; CloseGraph; end; close(inp); end.

P-I-4

Mezi jednotlivé části úlohy rozdělte body takto: část a 1 bod, část b 1 bod, část c 1 bod, část d 3 body, část e 4 body. V hodnocení je třeba klást důraz nejen na samotnou správnost sestrojených D0L systémů, ale i na jejich zdůvodnění (tj. důkaz, že růstová funkce navrženého D0L systému se chová tak, jak je to předepsáno v zadání). Pokud v částech a,b a c chybí, nebo je nedostatečné zdůvodnění, strhněte celkově za části a, b a c 1 bod. Pokud chybí popis v části d nebo e, strhněte 1-2 body za každý chybějící popis.

  1. Řešením je D0L systém ({a},{a-> a},a4).

    Tvrzení: V n-tém kroku je tvar slova a4 a tedy f(n)=4.

    Důkaz: Pro n=1 tvrzení zřejmě platí.

    Nechť dále wn=a4. Potom se uplatněním pravidla změní každé písmeno a na a a tedy wn+1=a4, čímž je tvrzení dokázáno.

  2. Řešením je D0L systém ({a,b},{a-> a,b-> ab},b).

    Tvrzení: V n-tém kroku je tvar slova an-1b a tedy f(n)=n

    Důkaz: Pro n=1 tvrzení zřejmě platí.

    Nechť dále $wn=an-1b. Potom se uplatněním pravidel změní každé písmeno a na a a písmeno b na ab a tedy wn+1=an-1ab=anb, čímž je tvrzení dokázáno.

  3. Řešením je D0L systém ({a,b},{a-> a,b-> a3b},a4,b).

    Tvrzení: V n-tém kroku je tvar slova a3n+1b a tedy f(n)=3n+2.

    Důkaz: Pro n=1 tvrzení zřejmě platí.

    Nechť dále $wn=a3n+1b. Potom se uplatněním pravidel změní každé písmeno a na a a písmeno b na a3b a tedy wn+1=a3n+1a3b=a3(n+1)+1b, čímž je tvrzení dokázáno.

  4. Řešením je D0L systém ({b,c,d},{b-> b, c-> bc, d-> bc2d},d).

    Tvrzení: V n-tém kroku je tvar slova b(n-1)^22c2(n-1)d a tedy f(n)=(n-1)2+2(n-1)+1=n2.

    Důkaz: Pro $n=1$ tvrzení zřejmě platí.

    Nechť dále wn=b(n-1)^2c2(n-1)d. Potom po uplatnění pravidel bude wn+1= b(n-1)^2b2(n-1)c2(n-1)bc2d= bn^2c2nd, čímž je tvrzení dokázáno.

    Poznámka: Ukážeme ještě postup, jak je možné tento D0L systém sestrojit. Platí:
    (n+1)2-n2=2n+1.
    To znamená, že při přechodu od n-tého k (n+1)-mu slovu musí ``přibýt'' 2n+1 písmenek. Kdybychom tedy našli systém, který má růstovou funkci f(n)=2n+1, potom by stačilo, aby každé jeho písmenko v každém kroku vygenerovalo nějaké ``neutrální'' písmenko (t.j. písmenko, které se v dalších krocích mění už jen samo na sebe). Takový stroj ale lehce sestrojíme: ({c,d},{c-> c,d-> c2 d},d) - důkaz tu nebudeme dělat, neboť je naprosto analogický s důkazy předcházejících tvrzení. Potom náš stroj bude vypadat takto: ({b,c,d},{b-> b,c-> bc, d-> bc2 d},d).

    Tento postup je možné rovněž použít jako důkaz správnosti, v mnoha případech je však jednodušší vzniklý D0L systém dokázat indukcí (viz výše). Ve skutečnosti ke konstrukci D0L systému v případě e) byl použit obdobný postup.

  5. Řešením je D0L systém ({b,c,d,e,f},{b-> b, c-> bde5f, d-> bd, e-> bde, f-> bde6f }, ck).

    Tvrzení: Pro n >= 2 je tvar slova bk(n-1)^3dk(3n^2-9n+7) ek(6n-7)fk. Jelikož f(1)=k, je f(n)=kn3 (k((n-1)3+3n2-9n+7+6n-7+1)= kn3 pro n >= 2).

    Důkaz: Pro n=1 a n=2 tvrzení zřejmě platí.

    Nechť tvrzení platí pro nějaké n >= 2. Potom wn=bk(n-1)^3dk(3n^2-9n+7)ek(6n-7)fk a po uplatnění pravidel wn+1= bk(n-1)^3bk(3n^2-9n+7)dk(3n^2-9n+7)bk(6n-7)dk(6n-7)ek(6n-7)bkdke6kfk=bkn^3dk(3n^2-3n+1)ek(6n-1)fk= bkn^3dk(3(n+1)^2-9(n+1)+7)ek(6(n+1)-7)fk, čímž je tvrzení dokázáno.