codeforces #341 div 2 D. Rat Kwesh and Cheese

Table of Contents

Note: This article is available in Chinese only. 本文暂无英文版本。 View original

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}

http://codeforces.com/contest/621/problem/D#

Related

http://codeforces.com/contest/621/problem/D
#