Code: Select all
/*
Author : Jan
Problem Name : Equations
Algorithm : Math
Complexity :
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max(a,b) ((a) > (b) ? (a) : (b))
#define CLR(a) memset(a,0,sizeof(a))
/* A Class with a/b format */
class fraction
{
public:
int a,b;
fraction()
{
a=0;
b=1;
}
fraction(int x)
{
a=x;
b=1;
}
fraction(int x,int y)
{
a=x;
b=y;
(*this).normalize();
}
void normalize();
fraction operator + (fraction);
fraction operator - (fraction);
fraction operator * (fraction);
fraction operator / (fraction);
bool operator == (fraction);
bool operator > (fraction);
bool operator < (fraction);
bool operator != (fraction);
};
int compare(fraction a,fraction b)
{
return a.a*b.b-a.b*b.a;
}
int gcd(int a,int b)
{
return (!b) ? a : gcd(b,a%b);
}
int lcm(int a,int b)
{
int d;
if(a<0) a=-a;
if(b<0) b=-b;
d=gcd(a,b);
d=a/d*b;
return d;
}
void fraction::normalize()
{
int d;
if(b==0)
b=1;
if(a==0)
{
b=1;
return;
}
if(b<0)
{
a*=-1;
b*=-1;
}
d=gcd(abs(a),abs(b));
a/=d;
b/=d;
}
fraction fraction::operator + (fraction X)
{
fraction Z;
Z.b=lcm(b,X.b);
Z.a=(Z.b/b)*a+(Z.b/X.b)*X.a;
Z.normalize();
return Z;
}
fraction fraction::operator - (fraction X)
{
fraction Z;
Z.b=lcm(b,X.b);
Z.a=(Z.b/b)*a-(Z.b/X.b)*X.a;
Z.normalize();
return Z;
}
fraction fraction::operator * (fraction X)
{
fraction Z;
Z.a=a*X.a;
Z.b=b*X.b;
Z.normalize();
return Z;
}
fraction fraction::operator / (fraction X)
{
fraction Z;
Z.a=a*X.b;
Z.b=b*X.a;
Z.normalize();
return Z;
}
bool fraction::operator == (fraction X)
{
return compare((*this),X)==0;
}
bool fraction::operator > (fraction X)
{
return compare((*this),X)>0;
}
bool fraction::operator < (fraction X)
{
return compare((*this),X)<0;
}
bool fraction::operator != (fraction X)
{
return compare((*this),X)!=0;
}
int cases,caseno;
char a[100000];
struct info
{
int a,b,c; // ax + by + c = 0
}A,B;
info check()
{
int sum;
int i,sign,flag,gotequal,k;
char *p,b[1000];
info A;
A.a=A.b=A.c=0;
p=strtok(a," ");
sign=gotequal=1;
while(p)
{
sscanf(p,"%s",b);
p=strtok(NULL," ");
if(b[0]=='=')
{
gotequal=-1;
sign=-1;
continue;
}
k=1;
if(b[0]=='+')
{
if(!b[1])
{
sign=1*gotequal;
continue;
}
i=1;
}
else if(b[0]=='-')
{
if(!b[1])
{
sign=-1*gotequal;
continue;
}
i=1;
k=-1;
}
else
i=0;
sum=flag=0;
for(;b[i];i++)
{
if(b[i]=='x')
{
flag=1;
break;
}
if(b[i]=='y')
{
flag=2;
break;
}
sum=sum*10+b[i]-48;
}
if(flag && !sum)
sum=1;
sum=sum*sign*k;
if(!flag)
A.c+=sum;
else if(flag==1)
A.a+=sum;
else
A.b+=sum;
}
return A;
}
void input()
{
gets(a);
gets(a);
A=check();
gets(a);
B=check();
}
inline void print(fraction k)
{
if(k.b==1)
printf("%d\n",k);
else
printf("%d/%d\n",k.a,k.b);
}
void process()
{
if(caseno++)
puts("");
if((!A.a && !A.b && A.c) || (!B.a && !B.b && B.c))
{
puts("don't know");
puts("don't know");
return;
}
fraction matrix[3][4],k,l;
if(!A.a && ( B.a || (!A.b && B.b)) )
{
info temp;
temp=A;
A=B;
B=temp;
}
matrix[1][1]=A.a;
matrix[1][2]=A.b;
matrix[1][3]=(-A.c);
matrix[2][1]=B.a;
matrix[2][2]=B.b;
matrix[2][3]=(-B.c);
if(matrix[1][1]!=0)
{
k=matrix[1][1];
matrix[1][1]=matrix[1][1]/k;
matrix[1][2]=matrix[1][2]/k;
matrix[1][3]=matrix[1][3]/k;
k=matrix[2][1]/matrix[1][1];
matrix[2][1]=matrix[2][1]-matrix[1][1]*k;
matrix[2][2]=matrix[2][2]-matrix[1][2]*k;
matrix[2][3]=matrix[2][3]-matrix[1][3]*k;
if(matrix[2][2]==0 && (matrix[2][3]!=0 || matrix[1][2]!=0))
{
puts("don't know");
puts("don't know");
return;
}
if(matrix[2][2]!=0)
{
l=matrix[2][3]/matrix[2][2];
k=matrix[1][3]-l*matrix[1][2];
print(k);
print(l);
}
else
{
print(matrix[1][3]);
puts("don't know");
}
}
else
{
puts("don't know");
if(matrix[1][2]==0)
{
puts("don't know");
return;
}
k=matrix[1][3]/matrix[1][2];
if(matrix[2][2]!=0)
{
l=matrix[2][3]/matrix[2][2];
if(l!=k)
{
puts("don't know");
return;
}
}
print(k);
}
}
int main()
{
scanf("%d",&cases);
while(cases--)
{
input();
process();
}
return 0;
}
