Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (1. soutěžní den) 46. ročníku

První soutěžní den - 24.4.1997

Všeobecné pokyny

Na řešení úloh 1. soutěžního dne celostátního kola MO-P máte 5 hodin čistého času. Z toho první půlhodina slouží k detailnímu seznámení se zadáním úloh, během této doby můžete klást dotazy směřující k upřesnění zadání. Řešení každého příkladu musí obsahovat (není-li přímo v zadání úlohy řečeno něco jiného) popis použitého algoritmu, zdůvodnění jeho správnosti (příp. důkaz algoritmu), diskusi o efektivitě zvoleného řešení (tzn. posouzení časových a paměťových nároků programu).

Kompletní program není nutnou součástí řešení, je však vhodnou formou přesného vyjádření popsaného algoritmu. Neuvedete-li program, musíte algoritmus zapsat jiným dostatečně přesným a detailním způsobem, aby z něj bylo zřejmé, jak si představujete programovou realizaci vašeho algoritmu. Program může být napsán v jazyce Pascal nebo C. Program nemusí zahrnovat celé řešení, je možné vynechat vstupy, výstupy a jednoduché technické operace (např. operace s množinami, implementace jednoduchých geometrických vztahů apod.). Slovní popis řešení musí být v každém případě jasný a srozumitelný i bez toho, že by bylo třeba nahlédnout do samotného programu.

P-III-1

Jsou dány souřadnice n modrých a n červených bodů v rovině. Žádné tři z těchto bodů neleží na jedné přímce a všechny jsou navzájem různé.

Napište co nejefektivnější algoritmus, který určí takových n úseček, že každá z nich má jeden koncový bod v červeném bodě a druhý v modrém bodě a žádné dvě úsečky nemají ani jeden společný bod. V případě, že řešení neexistuje, algoritmus o tom vypíše vhodnou zprávu.

Příklad

Vstup

n=2
modré body (0,0), (0,1)
červené body (1,1), (1,0)

Výstup

1.úsečka (0,0), (1,0)
2.úsečka (0,1), (1,1)

P-III-2

 Nechť A je posloupnost bodů v rovině A[1], A[2], ..., A[n], n >= 1, kde bod A[i] má celočíselné souřadnice (A[i].x,A[i].y). Tato posloupnost se nazývá schodovitá, jestliže pro každé i menší než n platí:
A[i].x < A[i+1].x
A[i+1].y < A[i].y
A[i+1].x - A[i].x <= 2
A[i].y - A[i+1].y <= 2
vzdálenost bodů A[i] a A[i+1] je menší než dvojnásobek druhé odmocniny ze dvou.

Je dán počáteční bod S s celočíselnými souřadnicemi (S.x, S.y) a koncový bod K se souřadnicemi (K.x, K.y). Napište co nejefektivnější algoritmus, který určí schodovitou posloupnost s nejmenším možným počtem bodů takovou, že jejím prvním bodem bude S a posledním bodem K (bude-li tedy mít posloupnost n bodů, potom A[1]=S a A[n]=K). V případě, že takováto posloupnost neexistuje, algoritmus o tom vypíše vhodnou zprávu. Důležitou součástí řešení je důkaz, že množina, kterou váš algoritmus najde, má skutečně nejmenší možný počet bodů.

Příklad

Vstup

S.x=0, S.y=2
K.x=4, K.y=0

Výstup

n=3
A[1].x=0, A[1].y=2
A[2].x=2, A[2].y=1
A[3].x=4, A[3].y=0

P-III-3

Kombinační obvody

Kombinační obvod se skládá ze vstupů obvodu (označených I1, I2,..., In), z hradel (označených H1, H2, ..., Hk) a z výstupů obvodu (označených O1, O2, ..., Om). Každé hradlo má jeden nebo více vstupů označených x1, x2,..., xp a jeden výstup označený z. Každý vstup hradla Hi je napojen buď na některý vstup obvodu nebo na výstup některého jiného hradla Hj, j < i. Každý výstup obvodu Oi je napojen na výstup některého hradla.

Vstupy a výstupy celého obvodu, stejně jako vstupy a výstupy jednotlivých hradel, se mohou nacházet v jednom ze dvou logických stavů 0 (false) nebo 1 (true). Výpočet obvodu je taktován. Jestliže jsou vstupy hradla H v čase t v logických stavech x1[t], x2[t], ..., xp[t], výstup hradla H bude v čase t+1 v logickém stavu z[t+1] určeném vstupy a typem hradla. Pokud je na tento výstup napojen například vstup x' hradla H', bude v čase t+1 vstup x' v logickém stavu z[t+1], tzn. logický stav se po spojnicích šíří bez zdržení.

Budeme používat tři typy hradel: NAND, NOR (s alespoň dvěma vstupy) a NOT (s jedním vstupem). Závislost výstupu těchto tří typů hradel na vstupech je popsána následující tabulkou (uvádíme příklady hradel NAND a NOR se dvěma a s třemi vstupy):

NAND

x1[t]x2[t]z[t+1]
001
011
101
110

NOR

x1[t]x2[t]z[t+1]
001
010
100
110

NOT

x[t]z[t+1]
01
10

NAND

x1[t]x2[t]x3[t]z[t+1]
0001
0011
0101
0111
1001
1011
1101
1110

NOR

x1[t]x2[t]x3[t]z[t+1]
0001
0010
0100
0110
1000
1010
1100
1110

Obecně hradlo typu NAND má výstupní hodnotu 0 právě tehdy, mají-li všechny jeho vstupy hodnotu 1. Hradlo typu NOR má výstupní hodnotu 1 právě tehdy, mají-li všechny jeho vstupy hodnotu 0.

Vstupem celého obvodu je n-tice logických stavů, v nichž se nacházejí jednotlivé vstupy obvodu I1, I2, ..., In. Logický stav vstupů obvodu se během výpočtu nemění. Hradla postupně reagují na logické stavy svých vstupů a mění podle toho stavy svých výstupů. Samozřejmě, jakmile se v čase t ustálí (tj. dále se nemění) logické stavy vstupů hradla, od okamžiku t+1 se ustálí také jeho výstup. Po konečném čase se ustálí i logické stavy výstupů obvodu. Výsledkem výpočtu je m-tice logických stavů jednotlivých výstupů obvodu O1, O2, ..., Om.

Příklad

Obr. č. 1.
Obr. č. 1
Například v případě obvodu na obrázku č.1 (hradla H1, H2 typu NAND se označují znakem &, hradlo H3 typu NOR označujeme symbolem 1) předpokládejme, že logické stavy vstupů obvodu jsou po řadě 0, 1, 1, 1. Od okamžiku t=1 bude logický stav výstupu hradla H1 roven 1 a logický stav výstupu H2 roven 0. Od okamžiku t=2 bude logický stav výstupu hradla H3 roven 0, což je také výsledek výpočtu.

Obr. č. 2.

Obr. č. 2
V obvodu na obrázku č.2 se objevují také hradla H3, H4 typu NOT (jsou označeny znakem 1, stejně jako hradla NOR, mají však pouze jeden vstup). Po dvou taktech (v čase t=2) se výstupy obvodu ustálí a výsledkem výpočtu bude "utříděný vstup": na výstupu O1 bude menší a na O2 větší z logických stavů na vstupech obvodu. Chování tohoto obvodu můžeme popsat tabulkou:

I1I2O1O2
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1

Soutěžní úloha

Navrhněte a popište kombinační obvody s 8 vstupy x1, x2, ..., x8 a s jedním výstupem pro následující funkce: