kmjp's blog

競技プログラミング参加記です

Codeforces #341 Div2. D. Rat Kwesh and Cheese

ある種一発アイデア問題。
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しました。

広告を非表示にする