比赛 |
2012Day1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
国王游戏 |
最终得分 |
100 |
用户昵称 |
阿狸 |
运行时间 |
1.147 s |
代码语言 |
C++ |
内存使用 |
15.91 MiB |
提交时间 |
2015-10-22 19:30:42 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
using namespace std;
const ll MOD=1000000;
int n;
int l,r;
struct edge{
ll l,r;
}q[1000100];
struct node{
int l;
ll k[10100];
}ans;
int com(edge a,edge b){
if(a.l*a.r==b.l*b.r)return a.l<b.l;
return a.l*a.r<b.l*b.r;
}
node C1(node a,int x){
node c=a;
for(int i=c.l;i>=1;--i){
c.k[i-1]+=c.k[i]%x*MOD;
c.k[i]=c.k[i]/x;
}
c.k[0]=0;
while(c.k[c.l]==0&&c.l)c.l--;
return c;
}
node C2(node a,int x){
node c=a;
for(int i=1;i<=c.l;++i)c.k[i]=c.k[i]*x;
for(int i=1;i<c.l;++i){
if(c.k[i]>=MOD){
c.k[i+1]+=c.k[i]/MOD;
c.k[i]%=MOD;
}
}
while(c.k[c.l]>=MOD){
c.k[c.l+1]+=c.k[c.l]/MOD;
c.k[c.l]%=MOD;
c.l++;
}
return c;
}
node M(node a,node b)
{
if(a.l>b.l)return a;
else if(a.l<b.l)return b;
else{
for(int i=a.l;i>=1;--i)
if(a.k[i]>b.k[i])return a;
else if(a.k[i]<b.k[i])return b;
else continue;
}
return a;
}
int main()
{
freopen("kinggame.in","r",stdin);
freopen("kinggame.out","w",stdout);
cin>>n;cin>>l>>r;
node a;
memset(a.k,0,sizeof(a.k));
memset(ans.k,0,sizeof(ans.k));
a.l=1;
a.k[1]=l;
ans.l=0;
for(int i=1;i<=n;++i)
cin>>q[i].l>>q[i].r;
sort(q+1,q+n+1,com);
for(int i=1;i<=n;++i)
{
node b=C1(a,q[i].r);
ans=M(ans,b);
a=C2(a,q[i].l);
}
printf("%lld",ans.k[ans.l]);
for(int i=ans.l-1;i>=1;--i)printf("%06d",ans.k[i]);
return 0;
}