Codeforces 799 D. Field expansion

题目链接：http://codeforces.com/contest/799/problem/D

因为${a_i>=2}$那么一个数字至多操作${log_{2}^{max(a,b)/min(h,w)}}$之后就会超过给定的${a,b}$，所以可以搜索，考虑复杂度问题我们就直接随机化，显然按照a_i的大小从大往小选。

辣鸡出题人没有把$h,w$旋转$90$度的情况放在PP里面，我的rating啊...

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<ctime>

 #include<cmath>

 #include<cstring>

 using namespace std;

 #define maxn 1001000

 #define llg long long

 #define inf 0x7fffffff

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 llg n,m,a[maxn],c,d,w,h,ans=inf,f[maxn];

 bool cmp(llg a,llg b) {return a>b;}

 inline int getint()

 {

        int w=,q=; char c=getchar();

        while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();

        while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;

 }

 void work()

 {

     llg cs=;

     llg x=c,y=d;

     while (x<h || y<w)

     {

         cs++;

         if (cs>n) return ;

         if (x>=h) {y*=a[cs]; continue;}

         if (y>=w) {x*=a[cs]; continue;}

         if (rand()%) x*=a[cs];else y*=a[cs];

     }

     ans=min(ans,cs);

 }

 int main()

 {

     yyj("D");

     cin>>h>>w>>c>>d>>n;

     for (llg i=;i<=n;i++) a[i]=getint(),f[a[i]]++;

     sort(a+,a+n+,cmp);

 //    n=min(n,(llg)40);

     while ((double)clock()/CLOCKS_PER_SEC<=0.91) work(),swap(h,w),work(),swap(h,w);

     if (ans==inf) ans=-;

     cout<<ans;

     return ;

 }