AOJ 1233 : Equals are Equals
問題リンク : Equals are Equals | Aizu Online Judge
問題概要 :
複数の数式が与えられる
一番最初の式が正しい答えで、その他の式がそれと同じかどうか判定せよ
細かい制約は略
解法 :
各変数に対してランダムに値を割り当て、式の結果が一致するかどうかチェックを行う
これを100回くらい行って全て一致していれば良いものとした
入力からとった式の適切な場所に*をつければただ構文解析するだけ
Kuala Lumpur でほぼ同じ問題があった
そっちもこんな感じでランダムの値を各変数に割り当てて解いた
一応、実際に変数のまま構文解析したコードも書いた
コード:
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; class Parsing{ private: string parse; int pos; public: Parsing(string s){ parse = s, pos = 0; } ll fact(){ if(parse[pos] == '('){ pos++; ll p = expression(); pos++; return p; }else{ ll p=0; while('0' <= parse[pos] && parse[pos] <= '9'){ p *= 10LL; p += parse[pos]-'0'; pos++; } return p; } } ll pow(){ ll p = fact(); while( parse[pos] == '^' ){ pos++; ll limit = fact(); ll tmp = 1LL; rep(_,limit) tmp *= p; p = tmp; } return p; } ll term(){ ll p = pow(); while(parse[pos] == '*' || parse[pos] == '/'){ if(parse[pos] == '*'){pos++;p *= pow();} else {pos++;p /= pow();} } return p; } ll expression(){ ll p = term(); while(parse[pos] == '+' || parse[pos] == '-'){ if(parse[pos] == '+'){pos++;p+=term();} else {pos++;p-=term();} } return p; } }; inline bool isNum(char c) { return '0' <= c && c <= '9'; } inline bool isVar(char c) { return 'a' <= c && c <= 'z'; } bool isMulti(char a,char b,bool flag){ if( flag && isNum(a) && isNum(b) ) return true; if( isNum(a) && isVar(b) ) return true; if( isVar(a) && isVar(b) ) return true; if( isVar(a) && isNum(b) ) return true; if( ( a == ')' ) && ( b == '(' ) ) return true; if( ( a == ')' ) && ( isNum(b) || isVar(b) ) ) return true; if( ( isNum(a) || isVar(a) ) && ( b == '(' ) ) return true; return false; } string Craftworks(string s){ string ret = "",tmp = ""; stringstream ss; ss << s; vector<string> buf; while( !(ss>>s).fail() ) buf.push_back(s); rep(i,buf.size()){ if( i+1 < buf.size() && isMulti(buf[i][(int)buf[i].size()-1],buf[i+1][0],true) ) { tmp += ( buf[i] + "*" ); } else tmp += buf[i]; } rep(i,tmp.size()){ if( i+1 < tmp.size() && isMulti(tmp[i],tmp[i+1],false) ) ret += string(1,tmp[i]) + "*"; else ret += string(1,tmp[i]); } return ret; } const int MOD = 10; string itos(int i) { stringstream ss; ss << i; return ss.str(); } int main(){ srand((unsigned int)time(NULL)); string s; while( 1 ){ vector<string> vec; while( getline(cin,s) ) { if( s == "." ) break; vec.push_back(s); } if( vec.empty() ) break; rep(i,vec.size()) vec[i] = Craftworks(vec[i]); vector<bool> verdict(vec.size(),true); rep(_,100){ vector<string> value(26); rep(i,26) value[i] = itos(rand() % MOD + 1); vector<ll> result; rep(i,vec.size()){ string buf; rep(j,vec[i].size()) { if( vec[i][j] == ' ' ) continue; if( 'a' <= vec[i][j] && vec[i][j] <= 'z' ) buf += value[vec[i][j]-'a']; else buf += vec[i][j]; } Parsing par(buf); result.push_back(par.expression()); if( i ) verdict[i] = verdict[i] & ( result[i] == result[0] ); } } REP(i,1,vec.size()) puts(verdict[i]?"yes":"no"); puts("."); } return 0; }