比赛 2012Day1 评测结果 AAAAAAAAAA
题目名称 国王游戏 最终得分 100
用户昵称 0 运行时间 0.585 s
代码语言 C++ 内存使用 36.54 MiB
提交时间 2015-10-22 19:56:16
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
int n;
 
struct at {
    int l,r;
}a[1010];
 
struct Data{
    int a[5010];
    friend Data operator * (Data a,Data b){
        Data c;
        memset(c.a,0,sizeof(c.a));
        for(int i=1;i<=a.a[0];i++)
            for(int j=1;j<=b.a[0];j++){
                c.a[i+j-1]+=a.a[i]*b.a[j];
                c.a[i+j]+=c.a[i+j-1]/10;
                c.a[i+j-1]%=10;
            }
        c.a[0]=a.a[0]+b.a[0];
        while(c.a[c.a[0]]==0)   c.a[0]--;
        return c;
    }
    friend Data operator / (Data a,int b){
        int yu=0;
        for(int i=a.a[0];i>0;i--){
            int t=yu*10+a.a[i];
            a.a[i]=(t)/b;
            yu=(t)%b;
        }
        while(!a.a[a.a[0]])     a.a[0]--;
        return a;
    }
     
}l[1010],r[1010],now,ans;
 
bool cmp(at a,at b)
{
    return a.r*a.l<b.l*b.r;
}
 
void change(int * a,int b)
{
    while(b){
        a[++a[0]]=b%10;
        b/=10;
    }
    return ;
}
 
bool PD(Data a,Data b)
{
    if(a.a[0]>b.a[0])    return true;
    if(a.a[0]<b.a[0])    return false;
    for(int i=a.a[0];i;i--){
        if(a.a[i]>b.a[i])    return true;
        if(a.a[i]<b.a[i])    return false;
    }
    return false;
}
 
void print(Data x)
{
    for(int i=x.a[0];i>0;i--)
        printf("%d",x.a[i]);
    printf("\n");
}
 
int main()
{
	freopen("kinggame.in","r",stdin);
	freopen("kinggame.out","w",stdout); 
    scanf("%d",&n);
    n++;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
    }
    sort(a+2,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        change(l[i].a,a[i].l);
    }
    now.a[0]=now.a[1]=1;
    for(int i=1;i<=n;i++){
        Data tp=now/a[i].r;
        if(PD(tp,ans))
            ans=tp;
        now=now*l[i];
    }
    print(ans);
    getchar();
    getchar();
    return 0;
}