== include(page="template/taskheader" task_id="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 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.
Poveste şi cerinţă...
h2. 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, codificare la fel.
Fişierul de intrare $vectori.in$ ...
h2. 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ă.
În fişierul de ieşire $vectori.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 1 000$
* $1 ≤ M ≤ N$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. vectori.in |_. vectori.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
1 0 1 1 1
| 1 1 1 1 1 0 0 0 0 0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Cele două relaţii 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$.
Ultimele $5$ relaţii nu pot fi obţinute din cele două date.
...
== include(page="template/taskfooter" task_id="vectori") ==
== include(page="template/taskfooter" task_id="vectori") ==
