Fişierul intrare/ieşire:	gauss.in, gauss.out	Sursă	Arhiva Educationala
Autor	Arhiva Educationala	Adăugată de	Gavrila Vlad •GavrilaVlad
Timp execuţie pe test	0.2 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Algoritmul lui Gauss

Se da un sistem de N ecuatii liniare cu M necunoscute. Notam necunoscutele cu x_i, 1 ≤ i ≤ M. Sa se determine, daca acest lucru este posibil, un set de valori ale necunoscutelor pentru care fiecare ecuatie este adevarata. Sistemul va fi dat sub forma unei matrici A cu N linii si M+1 coloane. Pe linia i a acestei matrici se va afla descrierea ecuatiei cu numarul i din sistem, astfel: A_i,1 * x₁ + A_i,2 * x₂ + ... + A_i,M * x_M = A_i,M+1.

Date de intrare

Pe prima linie a fişierului de intrare gauss.in se vor afla numerele N si M cu semnificatia din enunt. Pe urmatoarele N linii se vor afla cate M+1 intregi, descriind matricea A.

Date de ieşire

În fişierul de ieşire gauss.out se vor afisa M numere reale, cu precizia de 4 zecimale, reprezentand valorile sirului x, in cazul in care sistemul are solutie. In caz contrar, se va afisa mesajul "Imposibil".

Restricţii

• 1 ≤ N, M ≤ 100
• -100 ≤ A_i,j ≤ 100
• Solutia va fi considerata corecta daca, pentru fiecare i, 1 ≤ i ≤ N, rezultatul expresiei A_i,1 * x₁ + A_i,2 * x₂ + ... + A_i,M * x_M difera prin maxim 0.001 de A_i,M+1.

Exemplu

Explicatie

• 2 * 2 + 1 * 3 + (-1) * (-1) = 4 + 3 + 1 = 8
• (-3) * 2 + (-1) * 3 + 2 * (-1) = -6 - 3 - 2 = -11
• (-2) * 2 + 1 * 3 + 2 * (-1) = -4 + 3 - 2 = -3

Indicatii de rezolvare

Eliminarea Gaussiana este cel mai folosit algoritm pentru rezolvarea sistemelor de ecuatii liniare. Metoda reduce succesiv ecuatiile, lasand matricea initiala sub o forma din care vom putea afla usor valorile necunoscutelor. Astfel, notand cu p_i pozitia celui mai din stanga coeficient nenul de pe linia i, algoritmul garanteaza obtinerea urmatoarelor relatii: p₁ < p₂ < ... < p_N. Aceste pozitii vor fi chiar indicii necunoscutelor fixe, cele care pot lua o singura

Cum se trimit solutii?