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
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6double x,y,z;
7string ans[20];
1double cal( double a,double b,double c)
2{
3 return c*log(b)+log(log(a));
4}
5double cal2(double a,double b,double c)
6{
7 return log(b*c*log(a));
8}
1void pre()
2{
3 ans[1] = "x^y^z";
4 ans[2] = "x^z^y";
5 ans[5] = "y^x^z";
6 ans[6] = "y^z^x";
7 ans[9] = "z^x^y";
8 ans[10]= "z^y^x";
1 ans[3] ="(x^y)^z";
2 ans[4] ="(x^z)^y";
3 ans[7] ="(y^x)^z";
4 ans[8] ="(y^z)^x";
5 ans[11]="(z^x)^y";
6 ans[12]="(z^y)^x";
7}
8int dblcmp(double d)
9{
10 return d<-eps?-1:d>eps;
11}
12struct node
13{
14 double val;
15 int id;
16 node()
17 {
18 val = -9999999; //初始化是0不够小，虽然最大值一定大于0，但是比较的时候由于取了两次对数所以不一定大于0.
19 }
1 bool operator <(node b)const
2 {
3 int d = dblcmp(val-b.val);
4 if (d>0) return true;
5 if (d==0&&id<b.id) return true;
6 return false;
7 }
}a[20];
1bool cmp(node a,node b)
2{
3 int d = dblcmp(a.val-b.val);
4 if (d<0) return true;
5 if (d==0&&a.id<b.id) return true;
6 return false;
7}
8int main()
9{
10 #ifndef ONLINE_JUDGE
11 freopen("code/in.txt","r",stdin);
12 #endif
1 cin>>x>>y>>z;
2 pre();
3 for ( int i = 1 ; i <= 12 ; i ++) a[i].id = i ;
4 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;
1 a[4].val = cal2(x,z,y);
2 }
3 if (y>1)
4 {
5 a[5].val = cal(y,x,z);
6 a[6].val = cal(y,z,x);
7 a[7].val = cal2(y,x,z);
8 a[8].val = cal2(y,z,x);
9 }
10 if (z>1)
11 {
12 a[9].val = cal(z,x,y);
13 a[10].val = cal(z,y,x);
14 a[11].val = cal2(z,x,y);
15 a[12].val = cal2(z,y,x);
16 }
1 if (x>1||y>1||z>1)
2 {
3 sort(a+1,a+13);
4 }
5 else
6 {
7 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);
1 a[5].val = cal(1.0/y,x,z);
2 a[6].val = cal(1.0/y,z,x);
3 a[7].val = cal2(1.0/y,x,z);
4 a[8].val = cal2(1.0/y,z,x);
1 a[9].val = cal(1.0/z,x,y);
2 a[10].val = cal(1.0/z,y,x);
3 a[11].val = cal2(1.0/z,x,y);
4 a[12].val = cal2(1.0/z,y,x);
5 // for ( int i = 1 ; i <=12 ; i++) cout<<a[i].val<<endl;
6 sort(a+1,a+13,cmp);
}
cout<<ans[a[1].id]<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}