Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-03-08 16:41:53.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:operatie.in, operatie.outSursăFMI No Stress 9
AutorIoan Alexandru TifuiAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.15 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 2B, pe baza căruia a construit o matrice w de N linii şi N coloane, după următoarea regulă:

dacă (i + j) % 4 = 0dacă (i + j) % 4 = 2dacă (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 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.

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.inoperatie.out
3 4
0 15 8
15 11 12
8 15 0
11 11 8

Explicaţie:

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?