记录编号	192227	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]国王游戏	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.145 s
提交时间	2015-10-10 07:13:55	内存使用	8.29 MiB

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <string>
# include <iostream>
 
const int MAXN = 2010;
 
int n,ans;
int a[20000];
int b[20000];
int c[20000];
struct peo {
    int l,r,k;
    char bei[MAXN << 1];//前i个人的左手乘积
    char left[10];
    bool friend operator < (peo a,peo b) {
        return a.k < b.k;
    }
} ren[MAXN];
 
void cal(int x,int pos) {
    int i,j,k;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    a[0] = strlen(ren[x].bei);
    b[0] = strlen(ren[pos].left);
    for(i = 1; i <= a[0]; ++i) a[i] = ren[x].bei[a[0] - i] - 48;
    for(i = 1; i <= b[0]; ++i) b[i] = ren[pos].left[b[0] - i] - 48;
    for(i = 1; i <= a[0]; ++i) {
        k = 0;
        for(j = 1; j <= b[0]; ++j) {
            c[i + j - 1] += a[i] * b[j] + k;
            k = c[i + j - 1] / 10;
            c[i + j - 1] = c[i + j - 1] % 10;
        }
        c[i + b[0]] = k;
    }
    c[0] = a[0] + b[0];
    i = c[0];
    while(c[i] == 0 && i > 1) i--;
    c[0] = i;
    for(i = 0; i < c[0]; ++i) ren[x].bei[i] = c[c[0] - i] + 48;
}
 
void chu(int x) {
    int k = 0;
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));
    a[0] = strlen(ren[x].bei);
    for(int i = 0; i < a[0]; ++i) a[i + 1] = ren[x].bei[i] - 48;
    for(int i = 1; i <= a[0]; ++i) {
        c[i] = (k * 10 + a[i]) / ren[x].r;
        k = (k * 10 + a[i]) % ren[x].r;
    }
    int lenc = 1;
    while(c[lenc] == 0&& lenc < a[0]) lenc++;
    if(c[lenc] == 0) {
        printf("1");
        return ;
    }
    if(x == n)
        for(int i = lenc; i <= a[0]; ++i) printf("%d",c[i]);
}
 
void init() {
    int i,j;
    scanf("%d%d%d",&n,&ren[0].l,&ren[0].r);
    sprintf(ren[0].left,"%d",ren[0].l);
    for(i = 1; i <= n; ++i) {
        scanf("%d%d",&ren[i].l,&ren[i].r);
        ren[i].k = ren[i].l * ren[i].r;
        sprintf(ren[i].left,"%d",ren[i].l);
    }
    std::sort(ren + 1,ren + n + 1);
    ren[n].bei[0] = '1';
    for(j = 0; j < n; ++j) cal(n,j);
    chu(n);
}
 
int main() {
	freopen("kinggame.in","r",stdin);
	freopen("kinggame.out","w",stdout); 
    init();
}