operatie

Operatie

== include(page="template/taskheader" task_id="operatie") ==

Tică este un mare fan al operaţiilor pe biţi. într-o seară, pentru a scăpa de monotonie, acesta a luat un şir {*v*} de {*N*} numere naturale, strict mai mici decât *_2^B_^*, pe baza căruia a construit o matrice {*w*} de {*N*} linii şi {*N*} coloane, după următoarea regulă:

Tică the Trickster este un mare fan al operaţiilor pe biţi. Într-o seară, pentru a scăpa de monotonie, acesta a luat un şir {*v*} de {*N*} numere naturale, strict mai mici decât *_2^B_^*, pe baza căruia a construit o matrice {*w*} de {*N*} linii şi {*N*} coloane, după următoarea regulă:

|_. dacă (i + j) % 4 = 0 |_. dacă (i + j) % 4 = 2 |_. dacă (i + j) % 2 = 1 |
| w[i][j] = v[i] ^ v[j] | w[i][j] = v[i] & v[j] | w[i][j] = v[i] -> v[j] |

        {*} 1 -> 1 = 1
De exemplu, dacă B = 2 atunci 1 -> 1 = 3.

A doua zi, Tică îi arată foaia pe care este descrisă matricea {*w*} prietenului său Ionel şi îl provoaca pe acesta să ghicească şirul de numere iniţial. Tică este cunoscut ca o persoană căreia îi place să îşi păcălescă prietenii din când în când. Astfel există posibilitatea ca matricea pe care Tică i-o înmânează lui Ionel să nu poată fi soluţie pentru niciun şir de numere ce respectă proprietăţile de mai sus.

A doua zi, Tică îi arată foaia pe care este descrisă matricea {*w*} prietenului său Ionel şi îl provoaca pe acesta să ghicească şirul de numere iniţial. Tică este cunoscut ca o persoană căreia îi place să îşi păcălescă prietenii din când în când. Astfel există posibilitatea ca pentru matricea pe care Tică i-o înmânează lui Ionel să nu existe niciun şir care să o genereze respectând procesul descris mai sus.

Cunoscând numerele *N* şi *B*, precum şi matricea *w*, scieţi un program care să îl ajute pe Ionel să determine o posibilă soluţie pentru şirul *v* sau să specifice dacă o astfel de soluţie nu există.

 15 11 12
 8 15 0
| 11 11 8 |

| 10 10
0 382 128 575 681 127 576 639 178 62
975 368 671 885 1007 64 767 807 1023 0
128 885 0 869 8 877 740 887 18 869
1019 885 506 517 506 588 1022 517 1019 517
681 1015 8 663 0 735 104 727 539 663
1015 64 958 588 1022 73 1022 542 1015 0
576 497 740 901 104 457 0 983 626 385
1001 807 442 517 488 542 1022 599 1019 599
178 508 18 653 539 205 626 735 0 140
1023 0 1023 517 1023 0 1023 599 1023 0
| 961 368 154 517 360 73 638 599 883 0
|

h3. Explicaţie:

Reprezentările pe B biţi ale numerelor din v sunt:
v[0] = 1011
v[1] = 1011
v[2] = 1000

În primul exemplu, reprezentările pe B biţi ale numerelor din v sunt:
* v{~0~} = 1011
* v{~1~} = 1011
* v{~2~} = 1000

Observăm ca valorile din w corespund. De exemplu;

w[0][2] = (1011) & (1000) = 1000 = 8
w[1][2] = (1011) -> (1000) = 1100 = 12

* w{~0,2~} = (1011) & (1000) = 1000 = 8
* w{~1,2~} = (1011) -> (1000) = 1100 = 12

== include(page="template/taskfooter" task_id="operatie") ==