== include(page="template/taskheader" task_id="vectori") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $vectori.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $vectori.out$ ...
Î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ă.
h2. 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*.
h2. Exemplu
table(example). |_. vectori.in |_. vectori.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicaţie
...
Cele două relaţii date spun că
$v{~1~} + v{~2~} + v{~5~} = 0$
$v{~3~} + v{~4~} - v{~5~} = 0$.
Adunându-le, obţinem primele $5$ relaţii suplimentare:
$v{~1~} + v{~2~} + v{~3~} + v{~4~} = 0$.
Înmulţind prima relaţie cu $2$ obţinem ultima relaţie suplimentară:
$2 * v{~1~} + 2 * v{~2~} + 2 * v{~5~} = 0$
Relaţiile suplimentare $6 - 9$ nu pot fi obţinute din cele date.
== include(page="template/taskfooter" task_id="vectori") ==
== include(page="template/taskfooter" task_id="vectori") ==
