NOIP国王游戏

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'')

    {

        if(ch=='-') f=-;

        ch=getchar();

    }

    while(ch>='' && ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

struct node

{

    int a,b;

}f[];

bool cmp(node x,node y)

{

    return x.a*x.b<y.a*y.b;

}

int n,kinga,kingb,ans[],add[],sum[];

int i,k;

void cheng(int x)

{

    memset(add,,sizeof(add));

    int j;

    for(j=;j<=ans[];j++)

    {

        ans[j]*=x;

        add[j+]+=ans[j]/;

        ans[j]%=;

    }

    for(j=;j<=ans[]+;j++)//max 1000

    {

        ans[j]+=add[j];

        ans[j+]+=ans[j]/;

        ans[j]%=;

        if(ans[j]!=) ans[]=max(ans[],j);

    }

    return ;

}

void chu(int x)

{

    int j;

    memset(add,,sizeof(add));

    int q=;

    for(j=ans[];j>=;j--)

    {

        q*=;

        q+=ans[j];

        add[j]=q/x;

        if(add[]== && add[j]!=)

        {

            add[]=j;

        }

        q%=x;

    }

    return ;

}

bool my_max()

{

    if(sum[]>add[]) return ;

    if(sum[]<add[]) return ;

    int j;

    for(j=add[];j>=;j--)

    {

        if(add[j]<sum[j]) return ;

        if(add[j]>sum[j]) return ;

    }

    return ;

}

void my_ans()

{

    int j;

    memset(sum,,sizeof(sum));

    for(j=add[];j>=;j--)

        sum[j]=add[j];

    return ;

}

int main()

{

    n=read();

    f[].a=read(); f[].b=read();

    for(i=;i<=n;i++)

    {

        f[i].a=read();

        f[i].b=read();

    }

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

    ans[]=ans[]=;

    for(i=;i<=n;i++)

    {

        //cout<<"*"<<ans[0]<<"*";

        cheng(f[i-].a);

        chu(f[i].b);

        if(my_max())

        {

            my_ans();

        }

        //for(k=1;k<=ans[0];k++) cout<<add[k];

        //cout<<endl;

    }

    for(i=sum[];i>=;i--) printf("%d",sum[i]);

    return ;

}

国王游戏