Cod sursa(job #3303100)

Utilizator Iustin_Mircea2010Iustin Mircea Iustin_Mircea2010 Data 13 iulie 2025 19:13:57
Problema Algoritmul lui Gauss Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.14 kb
#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(10) << ans[i] << " ";
    }
    return 0;
}