SRM 287 DIV1 Easy - TwoEquations (復習○)

January 28, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=6013&rd=9808

・２次方程式が与えられる。
・このとき、ｘ、ｙを求める。
　ただし解がない時は"NO SOLUTIONS"、解が複数あるときは"MULTIPLE SOLUTIONS"を返す。

解き方

シミュレーションの問題なので、いかに簡単に実装するか。
ポイントは３つ。
１つめは、文字列から数字を取り出すところ。
２つめは、解がない時、複数あるときの例外判定。
３つめは、ｘ、ｙの求め方。

１つめについては数字の取り出しとかっこの判定を分けることで実装。
２つめ、３つめについては方程式を
Ax+ by= c、Dx+ ey= fとしたとき、
X= ce-bf / ae-bd,　Y= cd-af / bd-ae　となる。

２つめ、ae-bdが０のとき ce-bfかつcd-afが０であれば解が複数あり、そうでなければ解が存在しない。
またx,yのすべての係数が０のとき、右の項がすべて０なら解が複数あり、そうでなければ解が存在しない。

３つめについては上記の式でｘ、ｙを求めればよい。

コード

class TwoEquations {

public:

int getnum2(string str){
string org;
if(str[0]=='(')org=str.substr(1,2);
else org=str[0];
stringstream out(org);
int ans;
out>>ans;
return ans;
}

vector<int> getnum(string str){
stringstream out(str);
vector<int> ans(3,0);
string a0,a1,a2,b,c;
out>>a0>>b>>a1>>c>>a2;
ans[0]=getnum2(a0);
ans[1]=getnum2(a1);
ans[2]=getnum2(a2);
return ans;
}

string getans(int a,int b){
int gcd=1;
FORE(i,1,abs(b)+1)if(a%i==0&&b%i==0)gcd=i;
if(b<0)gcd=-gcd;
a/=gcd;
b/=gcd;
return getparse(a)+'/'+getparse(b);
}

string getparse(int x){
char ch[20];
if(x>=0)sprintf(ch,"%d",x);
else sprintf(ch,"(%d)",x);
return ch;
}

string solve(string first, string second) {
vector<int> a0(3,0),a1(3,0);

a0=getnum(first);
a1=getnum(second);

int num1=a0[0]*a1[1]-a0[1]*a1[0];
int num2=a0[2]*a1[1]-a0[1]*a1[2];
int num3=a0[2]*a1[0]-a0[0]*a1[2];

if(a0[0]==0&&a0[1]==0&&a1[0]==0&&a1[1]==0){
if(a0[2]==0&&a1[2]==0)return "MULTIPLE SOLUTIONS";
return "NO SOLUTIONS";
}
if(num1==0){
if(num2==0&&num3==0)return "MULTIPLE SOLUTIONS";
return "NO SOLUTIONS";
}

return "X="+getans(num2,num1)+" Y="+getans(num3,-num1);
}

};

実装