== include(page="template/taskheader" task_id="algebra") ==
Poveste si cerinta...
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{~K~}$ si matricile permutare corespunzatoare $P{~1~}, ..., P{~K~}$.
h2. Date de intrare
...
Prima linie a fisierului de intrare $algebra.in$ va contine numarul intreg $N$. Urmatoarele $N$ linii vor contine cate $N$ numere reale, reprezentand elementele matricii $A$, in ordine, de la linia $1$ la linia $N$ si de la coloana $1$ la coloana $N$. Elementele lui $A$ sunt date cu maxim $9$ zecimale.
h2. Date de iesire
...
Pe prima linie a fisierului de iesire $algebra.out$ veti afisa numarul intreg $K$. Pe urmatoarele $2*K$ linii veti afisa numerele $x{~1~},...,x{~K~}$ si matricile $P{~1~},..,P{~K~}$ , astfel: pe linia $2*i-1$ din cele $2*K$ veti afisa numarul real $x{~i~}$, cu cel putin $9$ zecimale. Pe linia $2*i$ veti descrie matricea $P{~i~}$ sub forma unui sir de $N$ numere intregi, separate prin cel putin un spatiu: $C{~1~} C{~2~} ... C{~N~}$. Valoarea $C{~j~}$ din acest sir va reprezenta coloana pe care se afla elementul egal cu $1$ de pe linia $j$ a matricei $P{~i~}$ .
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 30$
* 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]$.
h2. Exemplu
table(example). |_. algebra.in |_. algebra.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|3
0.4 0.5 0.1
0.3 0.3 0.4
0.3 0.2 0.5
| 5
0.300000000000
1 2 3
0.200000000000
2 1 3
0.300000000000
2 3 1
0.100000000000
1 3 2
0.100000000000
3 1 2
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="algebra") ==
