| Fişierul intrare/ieşire: | operatie.in, operatie.out | Sursă | FMI No Stress 9 |
| Autor | Ioan Alexandru Tifui | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Operatie
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 2B, 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] |
Prin '^' şi '&' se înţeleg operaţiile de XOR pe biţi şi respectiv de AND pe biţi.
Prin x -> y inţelegem urmăroarea operaţie:
• se consideră reprezentările binare ale lui x şi y pe B de biţi
• se efectuează implicaţia logica bit cu bit
• rezultatul se converteşte înapoi în baza 10
Implicaţia logică acţionează după regula:
• 0 -> 0 = 1
• 0 -> 1 = 1
• 1 -> 0 = 0
• 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 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ă.
Date de intrare
Fişierul de intrare operatie.in conţine pe prima linie numerele N şi B cu semnificaţia de mai sus.
Pe următoarele N linii se vor afla câte N numere naturale, reprezentând descrierea matricei w.
Date de ieşire
În fişierul de ieşire operatie.out se vor afla, pe o singură linie, N numere separate prin câte un spaţiu, reprezentând o posibilă soluţie pentru vectorul v, în cazul în care aceasta exista.
Dacă o astfel de soluţie nu există, fişierul va conţine doar valoarea -1.
Restricţii
- 2 ≤ N ≤ 1000
- 2 ≤ B ≤ 30
- Elementele vectorului v sunt indexate de la 0.
- Atât liniile cât şi coloanele matricei w sunt indexate de la 0.
- Pentru teste în valoare de 20 puncte N ≤ 5 şi B ≤ 4.
- Pentru alte teste în valoare de 20 de puncte N ≤ 1000 şi B ≤ 10.
Exemplu
| operatie.in | operatie.out |
|---|---|
| 3 4 0 15 8 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 |
Explicaţie:
În primul exemplu, reprezentările pe B biţi ale numerelor din v sunt:
* v0 = 1011
* v1 = 1011
* v2 = 1000
Observăm ca valorile din w corespund. De exemplu;
* w0,2 = (1011) & (1000) = 1000 = 8
* w1,2 = (1011) -> (1000) = 1100 = 12
