Fişierul intrare/ieşire:vectori.in, vectori.outSursăTabăra ICHB 2012, Ziua 2, Grupa 1
AutorDan Constantin SpatarelAdăugată despatarelDan-Constantin Spatarel spatarel
Timp execuţie pe test0.15 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Vectori

Greg îi tot explică lui Birkhoff că e mult mai deştept decât el... Birkhoff e sătul de replicile arogante ale lui Greg şi, ca să scape de el, îi propune următorul joc care să tranşeze problema odată pentru totdeauna: fiecare dintre cei doi aleg câte o problemă foarte grea pe care ştiu să o rezolve şi i-o dau celuilalt - primul care reuşeşte să rezolve corect problema propusă de celălalt va dovedi că este cel mai deştept!

Dar Birkhoff este mai înţelept: el are nevoie de linişte din partea lui Greg în următoarele ore pentru că are de pregătit o misiune foarte importantă. Ştiind că nu are de gând să rezolve problema propusă de Greg, v-aţi decis să-l ajutaţi pe Birkhoff rezolvând-o pentru el:

Se dau M relaţii despre N vectori nenuli în plan, distincţi doi câte doi. O astfel de relaţie între vectori spune că înmulţind fiecare dintre cei N vectori cu -1, 0 sau 1 şi adunând rezultatele se obţine vectorul nul.

Se mai ştie că pentru fiecare din cele M relaţii există un vector care în relaţia respectivă este înmulţit cu 1 iar în celelalte M - 1 relaţii cu 0.

Dându-se 10 relaţii suplimentare, se se determine pentru fiecare în parte dacă pot fi deduse din cele M sau nu.

Date de intrare

Fişierul de intrare vectori.in conţine pe prima linie două numere naturale: N şi M.
Pe următoarele M linii se găsesc cele M relaţii, câte una pe linie, codificate astfel: linia unei relaţii conţine N numere (-1, 0 sau 1), reprezentând coeficienţii cu care sunt înmulţiţi cei N vectori.
Pe următoarele 10 linii se găsesc relaţiile suplimentare.

Date de ieşire

În fişierul de ieşire vectori.out se va găsi o linie cu 10 numere (0 sau 1), reprezentând valorile de adevăr ale celor 10 relaţii suplimentare: 0 pentru o relaţie falsă şi 1 pentru o relaţie adevărată.

Restricţii

  • 5 ≤ N ≤ 1 000
  • 1 ≤ M ≤ N - 2
  • Coeficienţii care apar în relaţiile suplimentare sunt numere întregi cuprinse între -1 000 şi 1 000 inclusiv.

Exemplu

vectori.invectori.out
5 2
1 1 0 0 1
0 0 1 1 -1

1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
1 0 1 1 1
1 0 1 1 1
1 0 1 1 1
1 0 1 1 1
2 2 0 0 2
1 1 1 1 1 0 0 0 0 1

Explicaţie

Cele două relaţii date spun că
v1 + v2 + v5 = 0
v3 + v4 - v5 = 0.
Adunându-le, obţinem primele 5 relaţii suplimentare:
v1 + v2 + v3 + v4 = 0.

Înmulţind prima relaţie cu 2 obţinem ultima relaţie suplimentară:
2 * v1 + 2 * v2 + 2 * v5 = 0

Relaţiile suplimentare 6 - 9 nu pot fi obţinute din cele date.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?