Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-08 11:30:51.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:algebra.in, algebra.outSursă.campion 2003
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 = x1*P1 + ... + xK*PK, unde P1,P2,...,PK sunt matrici permutare (nu neaparat distincte) cu N linii si N coloane, iar x1, ..., xK sunt numere reale din intervalul [0,1] cu proprietatea ca x1 + ... + xK=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 x1, ..., xK si matricile permutare corespunzatoare P1, ..., PK.

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.

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 x1,...,xK si matricile P1,..,PK , astfel: pe linia 2*i-1 din cele 2*K veti afisa numarul real xi, cu cel putin 9 zecimale. Pe linia 2*i veti descrie matricea Pi sub forma unui sir de N numere intregi, separate prin cel putin un spatiu: C1 C2 ... CN. Valoarea Cj din acest sir va reprezenta coloana pe care se afla elementul egal cu 1 de pe linia j a matricei Pi .

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 Qi,j=x*Pi,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 Ri,j=Pi,j+Qi,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 xi si matricile Pi, astfel incat K ≤ N*(N-1)+1 .
  • Solutia furnizata de programul dumneavostra va fi considerata corecta daca, in urma efectuarii sumei x1*P1x2*P2...+xK*PK, fiecare element din matricea rezultata difera fata de elementul corespunzator din matricea A cu maxim 10-9 in valoare absoluta, suma x1x2...+xK se afla in intervalul [1.0-10-9,1.0+10-9] si fiecare valoarea xi se afla in intervalul [0,1].

Exemplu

algebra.inalgebra.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?