Državno natjecanje 2011. godine za 3. i 4. razred Srednje Škole - 2. zadatak - 2. dan

Inženjeri u Amtelu, najvedoj svjetskoj tvrtci za izradu integriranih krugova, dobili su zadatak osmisliti dizajn kruga za zbrajanje, temeljen na najnovijoj tehnologiji. Dostupne su im tri vrste logičkih krugova koji nose vrlo upečatljiva 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 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 broj n (1 <= n <= 256) koji predstavlja broj bitova broja A, a ujedno i broj bitova broja B.

U drugom retku nalazi se broj m, (m <= 10 000 000), koji predstavlja maksimalan broj logičkih krugova koji inženjeri smiju upotrijebiti.

IZLAZNI PODACI

U jednom retku, jedan cijeli broj koji predstavlja najmanji mogudi broj nivoa koji je potrebno upotrijebiti da bi se izvelo funkcionalno zbrajalo, ili broj -1 ako zbrajalo nije mogude izvesti. U taj broj se ubrajaju i ulazni nivo i izlazni nivo.

PRIMJERI TEST PODATAKA

ulaz

2
4

izlaz

5

ulaz

2
5

izlaz

4

ulaz

8
59

izlaz

6

Objašnjenje