Pagini recente » Cod sursa (job #3348794) | Cod sursa (job #3322190) | Cod sursa (job #3348836) | Cod sursa (job #3358173) | Cod sursa (job #3303099)
#include <bits/stdc++.h>
#define int long long
using namespace std;
//voi lucra cu fractii pentru acuratete maxima
struct fractie{
int a, b;
};
void normalize(fractie &x){ //simplificam
if(x.b < 0){
x.a *= -1;
x.b = -x.b;
}
int d = __gcd(abs(x.a), x.b);
if(d > 0){
x.a /= d;
x.b /= d;
}
}
fractie v[305][305];
int init[305]; //pe coloana i, sta de fapt necunoscuta init[i]
long double ans[305];
fractie sol[305];
signed main(){
ifstream cin("gauss.in");
ofstream cout("gauss.out");
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++) init[i] = i;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m + 1; j++){
int x;
cin >> x;
v[i][j].a = x;
v[i][j].b = 1;
}
}
bool posibil = true;
for(int i = 1; i <= min(n, m); i++){
//facem v[i][i] = 1
if(v[i][i].a == 0){
//gasim o alta ecuatie si/sau necunoscuta
int linie = -1, coloana = -1;
for(int ii = i; ii <= n; ii++){
for(int j = i; j <= m; j++){
if(v[ii][j].a){
linie = ii;
coloana = j;
break;
}
}
}
if(linie != -1){
swap(init[i], init[coloana]);
swap(v[i], v[linie]);
for(int ii = 0; ii < 305; ii++){
swap(v[ii][i], v[ii][coloana]);
}
}
else{
break;
}
}
//acum stim ca se poate
int a1 = v[i][i].a, b1 = v[i][i].b;
for(int j = i; j <= m + 1; j++){
v[i][j].b *= a1;
v[i][j].a *= b1;
normalize(v[i][j]);
}
for(int ii = i + 1; ii <= n; ii++){
fractie raport = v[ii][i];
raport.a *= -1;
normalize(raport);
for(int j = i; j <= m + 1; j++){
//v[ii][j] += raport * v[i][j]
fractie aux = raport;
aux.a *= v[i][j].a;
aux.b *= v[i][j].b;
normalize(aux);
int gcd = __gcd(v[ii][j].b, aux.b);
v[ii][j].a *= aux.b / gcd;
aux.a *= v[ii][j].b / gcd;
//am adus la acelasi numitor
v[ii][j].a += aux.a; //gata cu .a
v[ii][j].b *= aux.b / gcd; //gata cu .b, aici e de fapt v[ii][j].b = v[ii][j].b * aux.b / gcd;
normalize(v[ii][j]);
}
}
}
for(int i = 1; i <= n; i++){
bool ok = 1;
for(int j = 1; j <= m + 1; j++){
if(v[i][j].a){
ok = 0;
break;
}
}
if(ok){
swap(v[i], v[n]);
n--;
}
}
//mai verific inca o data
for(int i = 1; i <= min(n, m); i++){
if(v[i][i].a != v[i][i].b){
posibil = false;
break;
}
}
if(m < n){ //daca avem mai multe ecuatii decat necunoscute, ecuatiile in plus trebuie sa se rezolve singure
for(int i = m + 1; i <= n; i++){
if(v[i][m + 1].a != 0){
posibil = false;
break;
}
}
}
if(!posibil){
cout << "Imposibil\n";
return 0;
}
for(int i = min(n, m); i >= 1; i--){
fractie curr = v[i][m + 1];
for(int j = min(n, m); j > i; j--){
v[i][j].a *= sol[j].a;
v[i][j].b *= sol[j].b;
normalize(v[i][j]);
int gcd = __gcd(v[i][j].b, curr.b);
v[i][j].a *= curr.b / gcd;
curr.a *= v[i][j].b / gcd;
curr.a -= v[i][j].a;
curr.b *= v[i][j].b / gcd;
normalize(curr);
}
sol[i] = curr;
}
for(int i = min(n, m) + 1; i <= m; i++){
sol[i].a = 0;
sol[i].b = 1;
}
for(int i = 1; i <= m; i++){
ans[init[i]] = (long double)(sol[i].a) / (long double)(sol[i].b);
}
for(int i = 1; i <= m; i++){
cout << fixed << setprecision(9) << ans[i] << " ";
}
return 0;
}