Pro n=1 řešení zřejmě existuje. Předpokládejme tedy, že n > 1 a že tvrzení platí pro všechny množiny podle zadání s méně než 2n body. Posloupnost rozdělíme na k disjunktních souvislých neprázdných úseků tak, aby v každém úseku byl stejný počet červených a modrých bodů, ale v žádném kratším úseku začínajícím na stejném místě v posloupnosti nikoliv. Pokud k > 1, každý z těchto úseků obsahuje méně než 2n bodů, přičemž počet modrých a červených bodů je v každém úseku stejný. Podle indukčního předpokladu se tedy tedy v každém úseku dají body pospojovat předepsaným způsobem. Konvexní obaly jednotlivých úseků se nepřekrývají a úsečky spojující dva body z jednoho úseku leží celé v konvexním obalu tohoto úseku. Proto se úsečky spojující body z různých úseků neprotínají a řešení pro celou množinu A dostaneme jednoduše spojením řešení pro jednotlivé úseky.
Jestliže k=1, celá množina A tvoří jeden úsek. Lehce ukážeme, že první a poslední bod úseku mají různou barvu. První a poslední bod úseku jsou jistě vrcholy mnohoúhelníka tvořícího konvexní obal bodů obsažených v úseku. V tomto mnohoúhelníku proto jistě existují i dva za sebou jdoucí vrcholy různé barvy. Množina A', která vznikne odstraněním těchto dvou bodů z množiny A, už splňuje indukční předpoklad a existuje pro ni tedy řešení úlohy. Konvexní obal množiny A' nemá žádný společný bod s úsečkou spojující dva odstraněné body a proto přidáním této úsečky dostaneme řešení celé úlohy.
Popsaný důkaz již dává také návod k sestrojení algoritmu s časovou složitostí O(n2). Nejprve načteme souřadnice bodů a jejich barvu a uložíme je do pole A. Pole bodů uspořádáme a rozdělíme na úseky výše uvedeným způsobem. Rozdělení na úseky lze provést jedním průchodem polem A s průběžným počítáním počtu modrých a červených bodů. Nezpracované úseky si budeme odkládat do pomocného seznamu Z. Seznam můžeme realizovat v poli, neboť těchto úseků jistě nebude více než n. Úsek je určen indexy svých krajních bodů v poli A. Tato inicializační fáze vyžaduje čas O(n log n).
Dále postupně zpracováváme úseky ze seznamu Z. Ke každému úseku sestrojíme jeho konvexní obal, v něm najdeme dva sousední body různé barvy, spojíme je úsečkou a vyřadíme z množiny. Ze zbylých bodů opět vytvoříme stejným způsobem úseky a zařadíme je do seznamu Z. Tento postup opakujeme až do vyprázdnění seznamu Z.
Konvexní obal množiny m bodů uspořádaných podle x-ové souřadnice lze sestrojit v čase O(m). Nejlevější a nejpravější bod množiny (označme je L a P) jsou jistě vrcholy konvexního obalu. Ostatní body rozdělíme do dvou skupin podle toho, zda leží nad nebo pod přímkou LP. Nyní můžeme hledat zvlášť horní a zvlášť dolní část konvexního obalu. Postupně vždy procházíme uspořádanou skupinou bodů a do pomocného seznamu z nich vybíráme co nejvíce bodů tak, abychom zajistili konvexní vnitřní úhly pro každou trojici sousedních vybraných bodů.
Máme-li sestrojen konvexní obal, je v něm možné v čase O(n) nalézt dvojici sousedních bodů různé barvy, odstranit ji z pole a ze zbylých bodů vytvořit nové úseky. Zpracování jednoho úseku tedy vyžaduje čas nejvýše O(n) a výsledkem je jedna nalezená úsečka patřící do řešení úlohy. K nalezení všech n úseček tedy potřebujeme čas O(n2).
P-III-2
Schodovitá posloupnost zadaného typu může obsahovat pouze skoky
typů (1,2), (1,1) a (2,1) (otočíme souřadné osy tak, aby nás
znaménka neobtěžovala), na jejichž pořadí evidentně nezáleží
Každou takovou posloupnost spojující výchozí bod X
s cílovým bodem Y je proto možno jednoznačně popsat čísly a, b a c
udávajícími počty skoků jednotlivých typů a musí platit:
Vztah (1): (x,y) = Y - X = a (1,2) + b (1,1) + c (2,1)
Cílem tedy jest nalézt taková celá nezáporná čísla a, b, c splňující uvedenou podmínku, jejichž součet (to je vlastně celkový počet skoků, který máme minimalizovat -- označme si jej D) bude co nejmenší.
Nejprve si uvědomme, že pokud b > 2, posloupnost zaručeně optimální není - vybereme-li si nějakou trojici kroků typu b, můžeme ji nahradit jedním krokem typu a a jedním typu c, čímž D snížíme o 1.
Ze vztahu (1) plynou následující rovnice:
x = a + b + 2c
Vztah (2): y = 2a + b + c
Z toho získáme 2x - y = b + 3c, a proto:
c = 2x - y - b/3
Jenže c musí být celé číslo a tedy čitatel zlomku musí být
dělitelný třemi, což lze dosáhnout volbou b = 2x - y
mod 3 (je to jednoznačné, neboť víme, že 0 <= b < 3). Tím získáme
jednoznačné řešení pro c a dosazením do (2) také pro a.
Touto metodou jsme nalezli řešení úlohy, které je přípustné pokud a ani c nevyjdou záporná (v kterémžto případě úloha řešení nemá - snadno úpravou příslušných výrazů pro tyto proměnné zjistíte, že to nastává pouze pro x,y, které nejsou prvky intervalu < 1/2 ; 2 > . Navíc musí být i optimální, neboť pro b < 3 žádné jiné řešení rovnice (1) neexistuje a všechna řešení s b >= 3 jsou zaručeně horší.
Program ani nemá smysl uvádět, ježto pouze dosadí vstup do uvedených vztahů a každý úsek vypíše tolikrát, kolikrát vyšlo, že má být přítomen.
XOR se dvěma vstupy a jedním výstupem,
které má na výstupu 1 tehdy, je-li 1 na právě jednom
ze vstupů. Poté využijeme toho, že parita
vstupů x1, ..., x2n
je rovna funkci XOR
z parity x1,...,xn a
parity xn+1,...,x2n.
Tímto trikem paritu osmi vstupů snadno vypočteme "xorovacím
stromem". Pro vyřešení ještě zbývá výstup obvodu
znegovat, což snadno zařídíme nahrazením posledního hradla XOR
hradlem XNOR ("znegoavné" hradlo XOR -
na výstupu má 0, je-li 1 na právě jednom z jeho dvou
vstupů).NOR
testující alespoň jednu jedničku zopakované osmkrát (existuje 8 možností,
jak vypustit vstup) a jedno hradlo NOR ověřující, že všech 8 dílčích
podmínek je splněno.