Državno natjecanje 2014. godine za 1. i 2. razred Srednje Škole - 2. zadatak - 2. dan

Jure je odlučio u Hrvatskoj pokrenuti tvrtku Jur-tek za razvoj najnovijih elektroničkih integriranih krugova. Zaposlio je nekoliko domadih inženjera koji su dobili zadatak osmisliti dizajn kruga za zbrajanje, temeljen na najnovijoj tehnologiji. Dostupne su im tri vrste logičkih krugova koji nose vrlo upečatljiva i znakovita imena: Z0 , Z1 i K. Krugovi Z0 , Z1 imaju dva ulaza i dva izlaza, a logičke vrijednosti izlaza ovisno o onima na ulazu dane su prema ovim tablicama:

Krug Z0 možemo shvatiti kao da zbraja dva bita, dakle rezultat na izlazima može se protumačiti kao broj ulaza koji imaju logičku vrijednost 1. Kako postoje samo dva ulaza, to rezultat mogu biti samo brojevi 0, 1 ili 2, a u binarnom sustavu to se piše kao 00, 01 i 10.

Slično tomu, Krug Z1 možemo shvatiti kao da zbraja dva bita na ulazima i tome još pridodaje broj jedan.

Dakle, izlaz i2 ovih logičkih krugova predstavlja znamenku rezultata manje težine, a izlaz i1, predstavlja znamenku više težine koju je zatim potrebno pribrojiti drugim bitovima više težine želimo li ostvariti binarno zbrajalo.

Tri prethodna paragrafa su, naravno, samo pojašnjenje gornje dvije tablice koje o svemu navedenog precizno i točno govore same za sebe.

Krug K ima 3 ulaza: u0 , u1 i us , i izlaz i. Ako se na ulazu us nalazi logička vrijednost 0, onda de na izlazu i biti logička vrijednost istovjetna onoj na ulazu u0 a ako se na ulazu us nalazi logička vrijednost 1, tada de na izlazu i biti logička vrijednost istovjetna onoj na ulazu u1.

Inženjerima je zadano da osmisle zbrajalo koje zbraja dva cijela broja, A i B, koji nisu negativni. Brojevi su zadani binarnim sustavom pomodu točno n bitova svaki, tako da se logičke vrijednosti bitova nalaze na linijama ulaznog nivoa, dakle za broj A na linijama A1 – An i za broj B na linijama B1 - Bn.

Inženjeri zatim smještaju logičke krugove tipa Z0, Z1 i K u daljnje nivoe. Svaki ulaz logičkog kruga na nekom nivou smije biti povezan isključivo s nekim (bilo kojim) izlazom iz bilo kojeg prethodnog nivoa, ili s nekom linijom ulaznog nivoa.

U posljednjem, izlaznom nivou, nalaze se linije rješenja, njih točno n+1, označeni sa C1 – Cn+1. Za te linije vrijedi isto pravilo kao i za ulazne linije logičkih krugova: smiju biti povezane s nekim, bilo kojim, izlazom iz bilo kojeg prethodnog nivoa, ili s nekom linijom ulaznog nivoa.

ULAZNI PODACI

U prvom retku zadan je cijeli broj n (1 <= n <= 256) koji predstavlja broj bitova broja A, a ujedno i broj bitova broja B.

U drugom retku nalazi se cijeli broj m, (m <= 1000), koji predstavlja maksimalan broj nivoa koji inženjeri smiju upotrijebiti. U broj m se ubrajaju i ulazni nivo i izlazni nivo

IZLAZNI PODACI

U jednom retku, jedan cijeli broj koji predstavlja najmanji mogudi broj logičkih krugova koji je potrebno upotrijebiti da bi se izvelo funkcionalno zbrajalo, ili broj -1 ako zbrajalo nije mogude izvesti.

PRIMJERI TEST PODATAKA

ulaz

2
5

izlaz

4

ulaz

2
4

izlaz

5

ulaz

8
6

izlaz

59

![](i.ibb.co/QktvGGT/image.png