比赛 2012Day1 评测结果 AAAAAAAAAA
题目名称 国王游戏 最终得分 100
用户昵称 <蒟蒻>我要喝豆奶 运行时间 0.127 s
代码语言 C++ 内存使用 0.34 MiB
提交时间 2015-10-22 21:14:05
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
 
#define max(a,b) a<b?b:a
#define MAXC 5000
#define mod 10000
#define MAXN 1001
using namespace std;
 
int n;
struct BIGNUM{
    int len;
    int s[MAXC];
    void clear(void){
        len=1;
        memset(s,0,sizeof(s));
    }
    friend BIGNUM operator / (BIGNUM a,int b){
        for(int i=a.len-1;i>=0;i--){
            if(i>0)  a.s[i-1]+=(a.s[i]%b)*mod;
            a.s[i]/=b;
        }
        while(a.len>0&&a.s[a.len-1]==0) a.len--;
        if(a.len==0) a.len=1;
        return a;
    }
    friend bool operator < (BIGNUM a,BIGNUM b){
        if(a.len<b.len) return true;
        if(a.len>b.len) return false;
        int i;
        for(i=a.len-1;i>=0;i--){
            if(a.s[i]<b.s[i]) return true;
            if(a.s[i]>b.s[i]) return false;
        }
        return false;
    }
    friend BIGNUM operator * (BIGNUM a,int b){
        int i;
        for(i=0;i<a.len;i++) a.s[i]*=b;
        for(i=0;i<a.len||a.s[i]>0;i++){
            a.s[i+1]+=a.s[i]/mod;
            a.s[i]%=mod;
        }
        if(i>a.len) a.len=i;
        while(a.len>0&&a.s[a.len-1]==0) a.len--;
        if(a.len==0) a.len=1;
        return a;
    }
     
}ans;
struct king{
    int a,b;
    friend bool operator < (king x,king y){return x.a*x.b<y.a*y.b;}
}m[MAXN];
void ptr(void){
    BIGNUM now,tem;
    tem.clear(),tem.s[0]=1,ans.clear();
    tem=tem*m[0].a;
    for(int i=1;i<=n;i++){
        now=tem/m[i].b,ans=max(ans,now),tem=tem*m[i].a;
    }
    return ;
}
int main(){
	freopen("kinggame.in","r",stdin);
	freopen("kinggame.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        scanf("%d%d",&m[i].a,&m[i].b);
    sort(m+1,m+1+n);   
    ptr();
    printf("%d",ans.s[ans.len-1]); 
    for(int i=ans.len-2;i>=0;i--)
        printf("%.4d",ans.s[i]);
    return 0;
}