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 de pe fiecare coloana este egala cu 1. Matricea A se poate scrie ca o functie liniara de matrice permutare, adica A = x₁*P₁ + x₂*P₂ + .. + x_K*P_K, unde P₁, P₂, ..., P_K sunt matrice permutare (nu neaparat distincte) cu N linii si N coloane, iar x₁,x₂,..,x_K sunt numere reale din intervalul [0,1] cu proprietatea ca x₁+x₂+..+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 unica.

Cerinta

Dandu-se o matrice A avand proprietatile din enunt, sa se determine valoarea K, numerele reale x₁,x₂,..,x_K si matricele permutare corespunzatoare P₁,P₂,..,P_K.

Date de intrare

Prima linie a fisierului algebra.in va contine numarul intreg N. Urmatoarele N linii vor contine cate N numere reale, reprezentand elementele matricei 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.

Date de iesire

Pe prima linie a fisierului algebra.out veti afisa numarul intreg K. Pe urmatoarele 2*K linii veti afisa numerele x₁,..,x_K si matricele P₁,..,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₁ C₂ .. 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.

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 matrice 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₁*P₁+x₂*P₂+..+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₁+x₂+..+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].

Exemplu

Timp maxim de executie/test: 1 secunda 

Mugurel Ionut Andreica
student Universitatea Politehnica Bucuresti
Contact: mugurel_ionut at yahoo.com