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.
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月08日 星期一 03时38分46秒
4File Name :code/cf/#341/D.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33double x,y,z;
34string ans[20];
35
36double cal( double a,double b,double c)
37{
38 return c*log(b)+log(log(a));
39}
40double cal2(double a,double b,double c)
41{
42 return log(b*c*log(a));
43}
44
45
46void pre()
47{
48 ans[1] = "x^y^z";
49 ans[2] = "x^z^y";
50 ans[5] = "y^x^z";
51 ans[6] = "y^z^x";
52 ans[9] = "z^x^y";
53 ans[10]= "z^y^x";
54
55
56 ans[3] ="(x^y)^z";
57 ans[4] ="(x^z)^y";
58 ans[7] ="(y^x)^z";
59 ans[8] ="(y^z)^x";
60 ans[11]="(z^x)^y";
61 ans[12]="(z^y)^x";
62}
63int dblcmp(double d)
64{
65 return d<-eps?-1:d>eps;
66}
67struct node
68{
69 double val;
70 int id;
71 node()
72 {
73 val = -9999999; //初始化是0不够小，虽然最大值一定大于0，但是比较的时候由于取了两次对数所以不一定大于0.
74 }
75
76 bool operator <(node b)const
77 {
78 int d = dblcmp(val-b.val);
79 if (d>0) return true;
80 if (d==0&&id<b.id) return true;
81 return false;
82 }
83
84}a[20];
85
86
87
88bool cmp(node a,node b)
89{
90 int d = dblcmp(a.val-b.val);
91 if (d<0) return true;
92 if (d==0&&a.id<b.id) return true;
93 return false;
94}
95int main()
96{
97 #ifndef ONLINE_JUDGE
98 freopen("code/in.txt","r",stdin);
99 #endif
100
101 cin>>x>>y>>z;
102 pre();
103 for ( int i = 1 ; i <= 12 ; i ++) a[i].id = i ;
104 int cnt = 0 ;
105
106 if (x>1)
107 {
108
109 a[1].val = cal(x,y,z);
110 // cout<<"a[1].val:"<<a[1].val<<endl;
111
112 a[2].val = cal(x,z,y);
113
114 a[3].val = cal2(x,y,z);
115 // cout<<"a[3].val:"<<a[3].val<<endl;
116
117 a[4].val = cal2(x,z,y);
118 }
119 if (y>1)
120 {
121 a[5].val = cal(y,x,z);
122 a[6].val = cal(y,z,x);
123 a[7].val = cal2(y,x,z);
124 a[8].val = cal2(y,z,x);
125 }
126 if (z>1)
127 {
128 a[9].val = cal(z,x,y);
129 a[10].val = cal(z,y,x);
130 a[11].val = cal2(z,x,y);
131 a[12].val = cal2(z,y,x);
132 }
133
134 if (x>1||y>1||z>1)
135 {
136 sort(a+1,a+13);
137 }
138 else
139 {
140 a[1].val = cal(1.0/x,y,z);
141
142 a[2].val = cal(1.0/x,z,y);
143
144 a[3].val = cal2(1.0/x,y,z);
145
146 a[4].val = cal2(1.0/x,z,y);
147
148 a[5].val = cal(1.0/y,x,z);
149 a[6].val = cal(1.0/y,z,x);
150 a[7].val = cal2(1.0/y,x,z);
151 a[8].val = cal2(1.0/y,z,x);
152
153 a[9].val = cal(1.0/z,x,y);
154 a[10].val = cal(1.0/z,y,x);
155 a[11].val = cal2(1.0/z,x,y);
156 a[12].val = cal2(1.0/z,y,x);
157 // for ( int i = 1 ; i <=12 ; i++) cout<<a[i].val<<endl;
158 sort(a+1,a+13,cmp);
159
160 }
161
162 cout<<ans[a[1].id]<<endl;
163
164
165
166
167
168
169
170
171 #ifndef ONLINE_JUDGE
172 fclose(stdin);
173 #endif
174 return 0;
175}