2013-12-01 11:43:06Morris
[UVA][數學][繁瑣] 10367 - Equations
Problem A: Equations
Given 2 equations on the variables x and y, solve for x and y.The first line of input contains N, the number of test cases. Each test case consists of two equations, each on a separate line. An empty line separates cases. An equation consists of two or more terms separated by addition, subtraction, or equality operators. A term is an integer, or a variable name (x or y) optionally preceded by a minus sign or an integer coefficient. There is exactly one equality operator. All operators are surrounded by spaces, and there are no spaces within terms. For each case, print two lines, giving the values of x and y as rationals in simplest terms. If x or y has no unique rational value such that both equations hold, print "don't know" for its value. Print an empty line between cases.
Sample Input
7 2x + 3y = x 5 = x + y + 3 2x + 3y = 0 10x = -15y 2x + 3y = 0 10x = -15y + 1 x = 1 3x = 6y 2x = 3x + -x + y x + y = x + y 2x = -3 -2y = 3 1 = 2 x = 3
Output for Sample Input
3 -1 don't know don't know don't know don't know 1 1/2 don't know 0 -3/2 -3/2 don't know don't know
[UVa] 10367 - Equations、[POJ] 2347 - Equations
從來不曉得二元一次方程式那麼難解，
一般來說分成，有解、無解、無限多組解。
再來特別一點，「其中一個未知數有解」。
想說寫程式方便起見，用了高斯消去法，
夢魘就這麼開始了，當遇到 x = 2, x = 1 時，一消！ x 居然有解 orz。
請參考程式碼最下面的測資吧，輸入格式多少有點 *
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
class Frac {
public:
LL a, b;
Frac() {
a = 0, b = 1;
}
Frac(long long x, long long y) {
a = x, b = y;
reduce();
}
Frac operator+(const Frac &y) {
LL ta, tb;
tb = this->b/gcd(this->b, y.b)*y.b;
ta = this->a*(tb/this->b) + y.a*(tb/y.b);
Frac z(ta, tb);
return z;
}
Frac operator-(const Frac &y) {
LL ta, tb;
tb = this->b/gcd(this->b, y.b)*y.b;
ta = this->a*(tb/this->b) - y.a*(tb/y.b);
Frac z(ta, tb);
return z;
}
Frac operator*(const Frac &y) {
LL tx, ty, tz, tw, g;
tx = this->a, ty = y.b;
g = gcd(tx, ty), tx /= g, ty /= g;
tz = this->b, tw = y.a;
g = gcd(tz, tw), tz /= g, tw /= g;
//printf("%lld %lld ***********\n", tx*tw, ty*tz);
Frac z(tx*tw, ty*tz);
return z;
}
Frac operator/(const Frac &y) {
LL tx, ty, tz, tw, g;
tx = this->a, ty = y.a;
g = gcd(tx, ty), tx /= g, ty /= g;
tz = this->b, tw = y.b;
g = gcd(tz, tw), tz /= g, tw /= g;
//printf("%lld %lld ////////\n", tx*tw, ty*tz);
Frac z(tx*tw, ty*tz);
return z;
}
bool operator!=(const Frac &y) {
return this->a != y.a || this->b != y.b;
}
private:
static LL gcd(LL x, LL y) {
if(!y) return x;
if(x < 0) x *= -1;
if(y < 0) y *= -1;
LL t;
while(x%y)
t = x, x = y, y = t%y;
return y;
}
void reduce() {
LL g = gcd(a, b);
a /= g, b /= g;
if(b < 0) a *= -1, b *= -1;
}
};
void trim(char s[]) {
int i, j;
for(i = j = 0; s[i]; i++) {
if(s[i] != ' ')
s[j++] = s[i];
}
s[j] = '\0';
}
void parseEquation(char s[], long long *x, long long *y, long long *c) {
int i;
int sx, sy, sc;
int sign = 1, num = 0, f = 0;
int flag = 0;
sx = sy = sc = 0;
for(i = 0; s[i]; i++) {
if('0' <= s[i] && s[i] <= '9')
num = num*10 + s[i]-'0', f = 1;
else if(s[i] == '+') {
if(f) sc += sign*num*(flag ? -1 : 1), num = 0, f = 0, sign = 1;
sign *= 1;
} else if(s[i] == '-') {
if(f) sc += sign*num*(flag ? -1 : 1), num = 0, f = 0, sign = 1;
sign *= -1;
} else if(s[i] == 'x') {
if(f == 0) num = 1;
sx += sign*num*(flag ? -1 : 1), num = 0, f = 0, sign = 1;
} else if(s[i] == 'y') {
if(f == 0) num = 1;
sy += sign*num*(flag ? -1 : 1), num = 0, f = 0, sign = 1;
} else if(s[i] == '=') {
if(f) sc += sign*num, num = 0, f = 0, sign = 1;
sign = 1, num = 0, f = 0;
flag = 1;
}
}
if(f) sc += sign*num*(flag ? -1 : 1);
*x = sx, *y = sy, *c = sc;
//printf("%lld %lld %lld\n", *x, *y, *c);
}
char* fmt(const Frac &c) {
static char s[1024];
if(c.b == 1)
sprintf(s, "%lld", c.a);
else
sprintf(s, "%lld/%lld", c.a, c.b);
return s;
}
long long labs(long long a) {
return a < 0 ? -a : a;
}
void solve(Frac mtx[][3], Frac omtx[][3]) {
int n = 2, m = 3;
int i, j, k, deg = 0;
for(i = 0; i < n; i++) {// gaussian elimination.
k = i;
for(j = deg; j < n; j++) {
if(labs(mtx[j][i].a) > labs(mtx[k][i].a))
k = j;
}
if(mtx[k][i].a == 0)
continue;
else
deg++;
if(k != i) {
for(j = 0; j < m; j++)
swap(mtx[k][j], mtx[i][j]);
}
for(j = 0; j < n; j++) {
if(i == j) continue;
for(k = m-1; k >= i; k--) {
mtx[j][k] = mtx[j][k] - mtx[j][i]/mtx[i][i]*mtx[i][k];
}
}
}/*
for(int i = 0; i < n; i++, puts(" ---"))
for(int j = 0; j < m; j++)
printf("%s ", fmt(mtx[i][j]));*/
int solvable[2] = {1, 1};
if(mtx[1][1].a == 0)
solvable[1] = 0;
if(mtx[0][0].a == 0)
solvable[0] = 0;
else if(mtx[0][1].a && solvable[1] == 0)
solvable[0] = 0;
if(solvable[0] && solvable[1]) {
Frac rx = mtx[0][2]/mtx[0][0];
Frac ry = mtx[1][2]/mtx[1][1];
if(omtx[0][0]*rx+omtx[0][1]*ry != omtx[0][2])
solvable[0] = solvable[1] = 0;
if(omtx[1][0]*rx+omtx[1][1]*ry != omtx[1][2])
solvable[0] = solvable[1] = 0;
} else if(solvable[0]) {
Frac rx = mtx[0][2]/mtx[0][0];
if(omtx[0][1].a == 0) {
if(omtx[0][0]*rx != omtx[0][2])
solvable[0] = 0;
}
if(omtx[1][1].a == 0) {
if(omtx[1][0]*rx != omtx[1][2])
solvable[0] = 0;
}
} else if(solvable[1]) {
Frac ry = mtx[1][2]/mtx[1][1];
if(omtx[0][0].a == 0) {
if(omtx[0][1]*ry != omtx[0][2])
solvable[1] = 0;
}
if(omtx[1][0].a == 0) {
if(omtx[1][1]*ry != omtx[1][2])
solvable[1] = 0;
}
}
printf("%s\n", solvable[0] ? fmt(mtx[0][2]/mtx[0][0]) : "don't know");
printf("%s\n", solvable[1] ? fmt(mtx[1][2]/mtx[1][1]) : "don't know");
}
int main() {
int testcase;
char s[1024];
scanf("%d", &testcase);
while(getchar() != '\n');
while(testcase--) {
long long x1, y1, c1;
long long x2, y2, c2;
gets(s), trim(s);
parseEquation(s, &x1, &y1, &c1);
gets(s), trim(s);
parseEquation(s, &x2, &y2, &c2);
Frac mtx[2][3], omtx[2][3];
mtx[0][0] = Frac(x1, 1), mtx[0][1] = Frac(y1, 1), mtx[0][2] = Frac(-c1, 1);
mtx[1][0] = Frac(x2, 1), mtx[1][1] = Frac(y2, 1), mtx[1][2] = Frac(-c2, 1);
memcpy(omtx, mtx, sizeof(mtx));
solve(mtx, omtx);
if(testcase)
puts("");
gets(s);
}
return 0;
}
/*
20
x = y
x - y = 0
x = 2
2x = 4
0 = 0
y + x = x - y +8
-x = -y
x = y
1234x + 4567y = 7890
4321x + 7654y = 9876
1 = 2
0 = 0
x = 1
y = y+2
y = 1
x = x+1
x = 1
x = 1
x = 2
x = 1
71y = -82 - -17y + -3y + -26 + -10
29x - -8y + 49x = -78y - -57y + 66 - -47x - -80x
*/