codeforces #341 div 2 D. Rat Kwesh and Cheese
http://codeforces.com/contest/621/problem/D
题意：给出12个式子，问哪个最大。 思路：主要记住两个。一个是比较指数形式的数一个常用办法是取对数，同时要考虑是否能取对数，分情况讨论对于不能取对数的情况经过变换去取对数。第二个是取了两次对数后比较时候的最大值可能是小于0的。所以初始时置于0不够小。官方题解说得很清楚。
The tricky Rat Kwesh has finally made an appearance; it is time to prepare for some tricks. But truly, we didn't expect it to be so hard for competitors though. Especially the part about taking log of a negative number.We need a way to deal with x__y__z and x__yz. We cannot directly compare them, 200200200 is way too big. So what we do? Take log!
is an increasing function on positive numbers (we can see this by taking
, then
, which is positive when we are dealing with positive numbers). So if
, then x ≥ y.
When we take log,
But y__z can still be 200200, which is still far too big. So now what can we do? Another log! But is it legal? When x = 0.1 for example,
, so we cannot take another log. When can we take another log, however? We need
to be a positive number. y__z will always be positive, so all we need is for
to be positive. This happens when x > 1. So if_x_, y, z > 1, everything will be ok.
There is another good observation to make. If one of x, y, z is greater than 1, then we can always achieve some expression (out of those 12) whose value is greater than 1. But if x < 1, then x__a will never be greater than 1. So if at least one of x, y, z is greater than 1, then we can discard those bases that are less than or equal to 1. In this case,
. Remember that
, so
. Similarly,
.
The last case is when x ≤ 1, y ≤ 1, z ≤ 1. Then, notice that for example,
. But the denominator of this fraction is something we recognize, because 10 / 3 > 1. So if all x, y, z < 1, then it is the same as the original problem, except we are looking for the minimum this time.
/* ***********************************************
Author :111qqz
Created Time :2016年02月08日 星期一 03时38分46秒
File Name :code/cf/#341/D.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
double x,y,z;
string ans[20];
double cal( double a,double b,double c)
{
return c*log(b)+log(log(a));
}
double cal2(double a,double b,double c)
{
return log(b*c*log(a));
}
void pre()
{
ans[1] = "x^y^z";
ans[2] = "x^z^y";
ans[5] = "y^x^z";
ans[6] = "y^z^x";
ans[9] = "z^x^y";
ans[10]= "z^y^x";
ans[3] ="(x^y)^z";
ans[4] ="(x^z)^y";
ans[7] ="(y^x)^z";
ans[8] ="(y^z)^x";
ans[11]="(z^x)^y";
ans[12]="(z^y)^x";
}
int dblcmp(double d)
{
return d<-eps?-1:d>eps;
}
struct node
{
double val;
int id;
node()
{
val = -9999999; //初始化是0不够小，虽然最大值一定大于0，但是比较的时候由于取了两次对数所以不一定大于0.
}
bool operator <(node b)const
{
int d = dblcmp(val-b.val);
if (d>0) return true;
if (d==0&&id<b.id) return true;
return false;
}
}a[20];
bool cmp(node a,node b)
{
int d = dblcmp(a.val-b.val);
if (d<0) return true;
if (d==0&&a.id<b.id) return true;
return false;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
cin>>x>>y>>z;
pre();
for ( int i = 1 ; i <= 12 ; i ++) a[i].id = i ;
int cnt = 0 ;
if (x>1)
{
a[1].val = cal(x,y,z);
// cout<<"a[1].val:"<<a[1].val<<endl;
a[2].val = cal(x,z,y);
a[3].val = cal2(x,y,z);
// cout<<"a[3].val:"<<a[3].val<<endl;
a[4].val = cal2(x,z,y);
}
if (y>1)
{
a[5].val = cal(y,x,z);
a[6].val = cal(y,z,x);
a[7].val = cal2(y,x,z);
a[8].val = cal2(y,z,x);
}
if (z>1)
{
a[9].val = cal(z,x,y);
a[10].val = cal(z,y,x);
a[11].val = cal2(z,x,y);
a[12].val = cal2(z,y,x);
}
if (x>1||y>1||z>1)
{
sort(a+1,a+13);
}
else
{
a[1].val = cal(1.0/x,y,z);
a[2].val = cal(1.0/x,z,y);
a[3].val = cal2(1.0/x,y,z);
a[4].val = cal2(1.0/x,z,y);
a[5].val = cal(1.0/y,x,z);
a[6].val = cal(1.0/y,z,x);
a[7].val = cal2(1.0/y,x,z);
a[8].val = cal2(1.0/y,z,x);
a[9].val = cal(1.0/z,x,y);
a[10].val = cal(1.0/z,y,x);
a[11].val = cal2(1.0/z,x,y);
a[12].val = cal2(1.0/z,y,x);
// for ( int i = 1 ; i <=12 ; i++) cout<<a[i].val<<endl;
sort(a+1,a+13,cmp);
}
cout<<ans[a[1].id]<<endl;
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}