.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » algebra

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
algebra


Timp maxim de executie/test:
0.5 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

Cerinta

Dandu-se o matrice A avand proprietatile din enunt, sa se determine valoarea K, numerele reale x1,x2,..,xK si matricele permutare corespunzatoare P1,P2,..,PK.

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 x1,..,xK si matricele 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 matrice 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*P1+x2*P2+..+xK*PK, fiecare element din matricea rezultata difera fata de elementul corespunzator din matricea A cu maxim 10-9 in valoare absoluta, suma x1+x2+..+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.in algebra.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

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

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor