比赛 五一大礼包 评测结果 AAAAAWAAAA
题目名称 国王游戏 最终得分 90
用户昵称 彭欣越 运行时间 1.516 s
代码语言 C++ 内存使用 4.48 MiB
提交时间 2026-05-04 10:38:30
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010,M=100010;
ll n,x,y,ans;
ll sum=1,a[M],b[M],c[M],l1=1,l2,l3;
struct node {
    ll a,b;
}s[N];
bool cmp (node x,node y) {
    return x.a*x.b>y.a*y.b;
}
bool check () {
    if (l3<l2) return 1;
    if (l3>l2) return 0;
    for (int i=1;i<=l1;i++) {
        if (b[i]>c[i]) return 1;
        if (b[i]<c[i]) return 0;
    }
    return 0;
}
void jia (int x,int k) {
    int cnt=0;
    vector<int>v;
    while (x) {
        v.push_back(x%10);
        x/=10;
        cnt++;
    }
    v.push_back(0);
    for (int i=k;i<=k+cnt;i++) {
        if (v[i-k]>=10) {
            v[i-k]-=10;
            v[i-k+1]++;
        }
        if (b[i]+v[i-k]>=10) {
            v[i-k+1]++;
            b[i]+=v[i-k]-10;
        }else{
            b[i]+=v[i-k];
        }
    }
    if (b[k+cnt]) l2=k+cnt;
    else l2=k+cnt-1;
}
void cheng (int x) {
    memset(b,0,sizeof(b));
    for (int i=1;i<=l1;i++) {
        jia(a[i]*x,i);
    }
    l1=l2;
    for (int i=1;i<=l1;i++) a[i]=b[i];
}
void chu (int x) {
    l2=0;
    memset(b,0,sizeof(b));
    ll sum=0;
    for (int i=l1;i>=1;i--) {
        sum=sum*10+a[i];
        if (sum/x>=1) {
            b[i]=sum/x;
            l2=max(l2,(ll)i);  
        }
        sum%=x;
    }
}
int main () {
    freopen("kinggame.in","r",stdin);
    freopen("kinggame.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    a[1]=1;
    cin >> n;
    cin >> x >> y;
    cheng(x);
    for (int i=1;i<=n;i++) {
        cin >> s[i].a >> s[i].b;
        cheng(s[i].a);
    }
    //for (int i=l1;i>=1;i--) cout << a[i];
    //cout <<endl; 
    sort(s+1,s+1+n,cmp);
    for (int i=1;i<=n;i++) {
        chu(s[i].a);
        for (int j=1;j<=l1;j++) a[j]=b[j];
        l1=l2;
        chu(s[i].b);
        if (check()) {
            for (int j=1;j<=l2;j++) c[j]=b[j];
            l3=l2;
        }
    }
    for (int i=l3;i>=1;i--) cout << c[i];
    return 0;
}