ある種一発アイデア問題。
http://codeforces.com/contest/621/problem/D
問題
0.1~200の間の実数X,Y,Zが与えられる。
この3値を並べ替えて(A^B)^CまたはA^(B^C)の形の式を作るとき、最大値となる式を答えよ。
解法
もちろん愚直に行うと200^200^200等はオーバーフローする。
そこで全体のlogを取りつつ、全パターン試せばよい。
途中過程で200^200を取るのでdoubleでも心もとないため、long doubleを使おう。
logを2回取っても良いが、X,Y,Zのうち1未満のものがあると1回目のlogで負の値が出てしまい、2回目のlogが計算できなく泣くので気を付けよう。
long double X,Y,Z; string S[13]= { "", "x^y^z", "x^z^y", "(x^y)^z", "(x^z)^y", "y^x^z", "y^z^x", "(y^x)^z", "(y^z)^x", "z^x^y", "z^y^x", "(z^x)^y", "(z^y)^x", }; void solve() { int i,j,k,l,r,x,y; string s; cin>>X>>Y>>Z; pair<long double, int> P[9]; P[0]={-log(X)*pow(Y,Z),1}; P[1]={-log(X)*pow(Z,Y),2}; P[2]={-log(X)*(Y*Z),3}; P[3]={-log(Y)*pow(X,Z),5}; P[4]={-log(Y)*pow(Z,X),6}; P[5]={-log(Y)*(X*Z),7}; P[6]={-log(Z)*pow(X,Y),9}; P[7]={-log(Z)*pow(Y,X),10}; P[8]={-log(Z)*(X*Y),11}; sort(P,P+9); cout<<S[P[0].second]<<endl; }
まとめ
logに気づけばあっさり。
本番文字列配列の中身をタイプミスしてWAしました。