Pagini recente » Cod sursa (job #2322339) | Cod sursa (job #2186119) | Cod sursa (job #817766) | Cod sursa (job #2080613) | Cod sursa (job #2785507)
//
// Created by Mihai145 on 4/27/2021.
// Updated on 10/18/2021.
//
/*
* Test problem: https://infoarena.ro/problema/gauss
* Gaussian elimination to transform the system into an upper triangular matrix: O(N^3)
* Finds a solution for the system (or determines there is no solution)
*/
/*
* Updated: now we can solve for just the primary unknowns.
* The secondary unknowns will remain undetermined.
*/
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
const int NMAX = 300;
const double EPS = 1e-12;
bool NotNull(double x) { return x < -EPS || x > EPS; }
vector<double> res;
vector<bool> determined;
vector<bool> value_matters;
vector<bool> zero_set;
bool inconsistent;
void solveGauss(int N, int M, vector<vector<double>> sys) {
res.resize(M + 1, 0);
determined.resize(M + 1, false);
value_matters.resize(M + 1, true);
zero_set.resize(M + 1, false);
inconsistent = false;
int rank = 1;
for (int col = 1; col <= M && rank <= N; col++) {
for (int i = rank; i <= N; i++) {
if (NotNull(sys[i][col])) {
swap(sys[rank], sys[i]);
break;
}
}
if (NotNull(sys[rank][col]) == false) { ///value of unknown col doesn`t matter... we will consider it to be zero
determined[col] = false;
value_matters[col] = false;
zero_set[col] = true;
continue;
}
determined[col] = true;
long double ct = sys[rank][col];
for (int j = rank; j <= M + 1; j++) {
sys[rank][j] /= ct;
}
for (int i = 1; i <= N; i++) {
if (NotNull(sys[i][col]) == false || i == rank) {
continue;
}
long double ct = sys[i][col] / sys[rank][col];
for (int j = rank; j <= M + 1; j++) {
sys[i][j] -= ct * sys[rank][j];
}
}
rank++;
}
for (int i = rank; i <= N; i++) { ///system is inconsistent <=> 0 * x1 + 0 * x2 + ... + 0 * xm != 0
if (NotNull(sys[i][M + 1])) {
inconsistent = true;
}
}
for (int i = 1; i <= M; i++) {
if (!determined[i] && value_matters[i]) { ///more unknowns than equations... we will set these to zero
determined[i] = true;
zero_set[i] = true;
}
}
for (int j = 1; j <= M; j++) {
if (zero_set[j] == true) { ///changed j`s coef to 0, since it is 0 anyways...
for (int i = 1; i < rank; i++) {
///comment this line if need be
sys[i][j] = 0;
}
}
}
for (int i = 1; i < rank; i++) {
int f = 0, l = M;
for (; f <= M; f++) {
if (NotNull(sys[i][f])) {
break;
}
}
for (; l >= 1; l--) {
if (NotNull(sys[i][l])) {
break;
}
}
if (f == l) {
res[f] = sys[i][M + 1];
} else {
determined[f] = false; ///we cannot determine f, but we can determine some of the other unknowns...
}
}
}
int main() {
ifstream f("gauss.in");
ofstream g("gauss.out");
int N, M;
f >> N >> M;
vector<vector<double>> sys(N + 1, vector<double>(M + 2));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M + 1; j++) {
f >> sys[i][j];
}
}
solveGauss(N, M, sys);
bool all_unknowns_determined = true;
for (int i = 1; i <= M; i++) {
all_unknowns_determined &= determined[i];
}
if (!all_unknowns_determined || inconsistent) {
g << "Imposibil\n";
} else {
for (int i = 1; i <= M; i++) {
g << fixed << setprecision(10) << res[i] << ' ';
}
}
return 0;
}