Matematická olympiáda – kategorie P

Řešení úloh oblastního kola 42. ročníku

P-II-1

Označme si ai=|AAi| a bi=|ABi|. Dle zadání 0<=ai<bi pro každé i. V následujícím textu budeme jako objednávku j označovat tu objednávku, která patří městům Aj a Bj.

Myšlenka algoritmu je jednoduchá - dokud jsou nějaké nesplněné objednávky, přidáme další jízdu a simulujeme cestu auta z A do B. Pokud je auto v nějakém městě volné, vybereme si jako další objednávku z dosud nesplněných tu, která začíná co nejdříve.

Efektivní implementace této myšlenky vede k příliš složitému programu. Proto nebudeme přiřazovat objednávky jízdám, ale naopak. Čísla a1,...,an a b1,...,bn uspořádáme vzestupně a potom procházíme úsek od A do B. Přitom si udržujeme zatím potřebný počet jízd v proměnné p a seznam "volných jízd" (na začátku prázdný). Jestliže narazíme na město Ai a seznam je prázdný, zvýšíme počet jízd na p+1 a i-tou objednávku splníme v této jízdě. Jestliže narazíme na město Bi, jízdu, kterou jsme splnili i-tou objednávku, "uvolníme", tj. přidáme do seznamu volných jízd.

Poznámky k implementaci

Důkaz správnosti algoritmu

Algoritmus zřejmě nalezne nějaký korektní plán, neboť každé objednávce přiřadí právě jednu jízdu a jízda, které je přiřazena, je v dané chvíli volná.

Nyní dokážeme optimalitu získaného plánu. Označme k0=max |{i|x je v (ai,bi>}| pro x v <0,|AB|> (maximální počet intervalů s neprázdným průnikem). Zřejmě potřebujeme alespoň k0 jízd. Ukážeme, že algoritmus nalezne plán s přesně k0 jízdami.

Uvažujme takové i, že počet jízd (proměnná p) se zvyšuje z p na p+1 při přidání bodu ai. Tehdy není k dispozici žádná volná jízda, tedy bod ai leží v nějakých intervalech <akj,bkj) pro j=1,...,p0. Bod ai+e, kde e je dostatečně malé číslo, leží uvnitř těchto p intervalů a navíc v intervalu (ai,bi>, tedy p+1<=k0, tedy hodnota p nikdy nevzroste nad k0.

Odhad časové složitosti: odhlédneme-li od třídění, pro každý prvek ai nebo bi vykonáme konstantní množství operací, tedy O(n). Složitost třídění je O(n log n), dohromady tedy máme časovou složitost O(n log n).

Paměťová složitost je lineární.

P-II-2

Vzdálenost bodu X od přímky YZ označme d(X,YZ), průmět rovinného útvaru X na přímku p označme pr(X,p), orientovanou vzdálenost bodu C od AB označme vzdal(A,B,C); platí d(C,AB)=|vzdal(A,B,C)| a znaménko vzdal je kladné pro C vlevo od AB a záporné pro C vpravo od AB.

Dále předpokládejme, že vrcholy M jsou uspořádány proti směru hodinových ručiček a položme Xn+1=X1.

Pro každé 1<=i<=n určíme čísla šířkai=max d(Xj,XiXi+1) pro 1<=j<=n a průměti=|pr(M,XiXi+1)|. Hledaná délka strany S je potom minimax{šířkai,průměti} pro 1<=i<=n.

Pro každý index i určíme indexy di, li a pi následovně:

Body Xli a Xpi se dají charakterizovat také takto: Zvolíme si bod X' vlevo od přímky XiXi+1 tak, aby XiXi+1 bylo kolmé na XiX'. Potom Xli (Xpi) je nejvzdálenější bod M ležící nalevo (napravo) od přímky XiX'. Tedy šířkai=d(Xdi,XiXi+1)=vzdal(Xi,Xi+1,Xdi) a průměti=d(Xli,XiX')+d(Xpi,XiX')=vzdal(Xi,X',Xli)-vzdal(Xi,X',Xpi).

Zbývá určit, jak od indexů di, li, pi pro i přejít k indexům di+1, li+1 a pi+1 pro i+1. Představme si přímku, která se otáčí z polohy XiXi+1 do polohy Xi+1Xi+2. Vrchol M nejvzdálenější od této přímky se postupně přesouvá z polohy Xdi do polohy Xdi+1. Novou hodnotu di+1 určíme z podmínky d(Xdi+1,Xi+1Xi+2)>=d(Xdi+1 +1,Xi+1Xi+2). Podobně určíme i li+1, pi+1. Na základě těchto úvah již snadno sestrojíme program řešící zadanou úlohu.

Časová složitost: Indexy di, li a pi "obejdou" M právě jednou a jejich počáteční nastavení nám zabere nejvýše lineární čas, tedy O(|M|). Paměťová složitost: kromě množiny M si ukládáme pouze konstantní množství dat, tedy O(|M|).

P-II-3


  1. f22=a11b11+a12b21
    f23=a21b11+a22b21
    f24=a11b12+a12b22
    f25=a21b12+a22b22
    Tedy:
    (f22f24)=(a11a12)*(b11b12)
    (f23f25)(a21a22)(b21b22)
    Výsledkem programu je tedy vynásobení dvou matic.
  2. Jestliže je n sudé, potom n/2-krát použijeme algoritmus z části a) postupně pro vstup xi, xi+1, yi, yi+1, ui, vi, ui+1, vi+1 pro i=1,3,...,n-1 a pomocí 7n/2 násobení získáme xiui+xi+1ui+1, xivi+xi+1vi+1, yiui+yi+1ui+1, yivi+yi+1vi+1 (i=1,3,...,n-1) a sečtením příslušných mezivýsledků dostáváme požadované součty. Je-li n liché, určíme tímto postupem součty pro n-1 prvních čísel a pomocí dalších 4 násobení xnun,ynun,xnvn,ynvn získáme požadované součty pomocí (7n+1)/2 násobení.

P-II-4

  1. Jestliže Y->AMY, tak MY->M(AMY) podle definice operace M(). Stačí tedy pomocí McCullochova zákona nalézt takové Y a položit X=MY; např. X=M572AM572 nebo X=M752AM7522.
  2. Zřejmě 2X2->X (pravidlo P1); stačí tedy nalézt takové X, že X->2X2. Ovšem 2X2=7(2X) a můžeme použít Craigův zákon s M=7, A=2. Dostáváme X=757227572 nebo X=7752277522.
  3. Postupujeme obdobně: 2BX2->BX, hledáme X tak, aby X->A2BX2=7(A2BX). Craigův zákon s M=7, A=A2B dává řešení X=7572A2B7572 nebo X=7752A2B77522.