Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | vectori.in, vectori.out | Sursă | Tabăra ICHB 2012, Ziua 2, Grupa 1 |
| Autor | Dan Constantin Spatarel | Adăugată de |  Dan-Constantin Spatarel •spatarel |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/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.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 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.
Ultimele 4 relaţii suplimentare nu pot fi obţinute din cele date.
Înmulţind prima relaţie cu 2 obţinem ultima relaţie suplimentară:
2 * v1 + 2 * v2 + 2 * v5 = 0
