== include(page="template/taskheader" task_id="algebra") ==

Se da o matrice patratica $A$ cu elemente reale din intervalul $[0,1]$ , avand $N$ linii si $N$ coloane. Suma elementelor de pe fiecare linie si fiecare coloana este egala cu $1$. $A$ se poate scrie ca o functie liniara de matrici permutare, adica $A=x{~1~}*P{~1~}+x{~2~}*P{~2~}+...+x{~K~}*P{~K~}$, unde $P{~1~},P{~2~},...,P{~K~}$ sunt matrici permutare (nu neaparat distincte) cu $N$ linii si $N$ coloane, iar $x{~1~},x{~2~},..,x{~K~}$ sunt numere reale din intervalul $[0,1]$ cu proprietatea ca $x{~1~}+x{~2~}+...+x{~K~}=1$. O matrice permutare cu $N$ linii si $N$ coloane contine exact $N$ elemente de $1$, cate unul pe fiecare linie si fiecare coloana, iar restul elementelor sunt egale cu $0$. Scrierea matricei $A$ in forma precizata nu este neaparat unica.

Se da o matrice patratica $A$ cu elemente reale din intervalul $[0,1]$ , avand $N$ linii si $N$ coloane. Suma elementelor de pe fiecare linie si fiecare coloana este egala cu $1$. $A$ se poate scrie ca o functie liniara de matrici permutare, adica $A = x{~1~}*P{~1~} + ... + x{~K~}*P{~K~}$, unde $P{~1~},P{~2~},...,P{~K~}$ sunt matrici permutare (nu neaparat distincte) cu $N$ linii si $N$ coloane, iar $x{~1~}, ..., x{~K~}$ sunt numere reale din intervalul $[0,1]$ cu proprietatea ca $x{~1~} + ... + x{~K~} = 1$. O matrice permutare cu $N$ linii si $N$ coloane contine exact $N$ elemente de $1$, cate unul pe fiecare linie si fiecare coloana, iar restul elementelor sunt egale cu $0$. Scrierea matricei $A$ in forma precizata nu este neaparat unica.

Dandu-se o matrice $A$ avand proprietatile din enunt, sa se determine valoarea $K$, numerele reale $x{~1~},x{~2~},...,x{~K~}$ si matricile permutare corespunzatoare $P{~1~},P{~2~},...,P{~K~}$.

Dandu-se o matrice $A$ avand proprietatile din enunt, sa se determine valoarea $K$, numerele reale $x{~1~}, ..., x{~K~}$ si matricile permutare corespunzatoare $P{~1~}, ..., P{~K~}$.

h2. Date de intrare

* Rezultatul inmultirii unui numar real $x$ cu o matrice $P$ avand $N$ linii si $N$ coloane este o matrice $Q$ cu $N$ linii si $N$ coloane, avand elementele $Q{~i,j~}=x*P{~i,j~}$ .
* Rezultatul adunarii a doua matrici $P$ si $Q$ cu $N$ linii si $N$ coloane este o matrice $R$ cu $N$ linii si $N$ coloane, avand elementele $R{~i,j~}=P{~i,j~}+Q{~i,j~}$ .
* Nu este impusa o limita superioara pentru valoarea lui $K$ . Totusi, se poate demonstra ca, oricare ar fi matricea $A$ avand proprietatile specificate, exista valorile $x{~i~}$ si matricile $P{~i~}$, astfel incat $K ≤ N*(N-1)+1$ .

* Solutia furnizata de programul dumneavostra va fi considerata corecta daca, in urma efectuarii sumei $x{~1~}*P{~1~}+x{~2~}*P{~2~}+...+x{~K~}*P{~K~}$, fiecare element din matricea rezultata difera fata de elementul corespunzator din matricea $A$ cu maxim $10{^-9^}$ in valoare absoluta, suma $x{~1~}+x{~2~}+...+x{~K~}$ se afla in intervalul $[1.0-10{^-9^},1.0+10{^-9^}]$ si fiecare valoarea $x{~i~}$ se afla in intervalul $[0,1]$.

* Solutia furnizata de programul dumneavostra va fi considerata corecta daca, in urma efectuarii sumei $x{~1~}*P{~1~} + x{~2~}*P{~2~} + ... + x{~K~}*P{~K~}$, fiecare element din matricea rezultata difera fata de elementul corespunzator din matricea $A$ cu maxim $10^-9^$ in valoare absoluta, suma $x{~1~} + x{~2~} + ... + x{~K~}$ se afla in intervalul $[1.0-10^-9^,1.0+10^-9^]$ si fiecare valoarea $x{~i~}$ se afla in intervalul $[0,1]$.

h2. Exemplu

== include(page="template/taskfooter" task_id="algebra") ==

2172