inmultire

Time limit: 0.2s Memory limit: 128MB Input: inmultire.in Output: inmultire.out

Cerință

Se dă nn și o matrice binară, numită cc, cu nn linii și nn coloane. Aflați dacă există două șiruri binare aa și bb de lungime nn astfel încât aibj=ci,ja_i \cdot b_j = c_{i,j} pentru fiecare 1i,jn1 \leq i, j \leq n. Dacă nu există două astfel de șiruri, afișați 1.

Date de intrare

Pe prima linie a fișierului de intrare inmultire.in se află numărul nn. Pe următoarele nn linii se află câte nn elemente, reprezentând matricea cc.

Date de ieșire

Să se afișeze -1 în fișierul inmultire.out dacă nu există soluție, altfel pe prima linie să se afișeze șirul aa și pe a doua linie să se afișeze șirul bb. Dacă există mai multe soluții, se poate afișa oricare.

  • 2n1 0002 \leq n \leq 1 \ 000
  • 0ci,j10 \leq c_{i, j} \leq 1

Restricții și precizări

# Punctaj Restricții
1 10 n=1n = 1
1 20 n=2n = 2
3 70 Fără restricții suplimentare

Exemplul 1

inmultire.in

2
0 0
1 1

inmultire.out

0 1
1 1

Explicație

La primul exemplu, avem a=[0,1]a = [0, 1] și b=[1,1]b = [1, 1]. c1,1=a1b1=0c_{1, 1} = a_1 \cdot b_1 = 0, c1,2=a1b2=0c_{1, 2} = a_1 \cdot b_2 = 0, c2,1=a2b1=1c_{2, 1} = a_2 \cdot b_1 = 1 și c2,2=a2b2=1c_{2, 2} = a_2 \cdot b_2 = 1. Deci, soluția aceasta este bună.

Exemplul 2

inmultire.in

5
1 0 0 1 1
1 0 0 1 1
1 0 0 1 1
0 0 0 0 0
1 0 0 1 1

inmultire.out

1 1 1 0 1
1 0 0 1 1

Exemplul 3

inmultire.in

2
1 0 
0 1

inmultire.out

-1

Explicație

La al treilea exemplu, se poate demonstra că nu există soluție. Așadar, afisăm -1.

Log in or sign up to be able to send submissions!