记录编号	124254	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]国王游戏	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2014-10-02 20:41:53	内存使用	3.74 MiB

/*
倒不等式 
max{s(i-1) - b(i), s(j-1) - b(j)} >=  max{s(i-1) - b(j), s(j-1) - b(i)}
s2(j-1) = s(j-1) - a(i) + a(j)
1.s(i-1) < s(j-1)
2.b(j) > b(i), s(i-1) - b(j) < s(j-1) - b(j)
所以当 b(i)+a(i) > a(j)+b(j) (i<j时交换)
所以以 b(i)+a(i) 为关键字，从大到小排列，即得出结果排列 
注意是乘法，用高精度。 
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

#define Maxn 1002

using namespace std;

int n;

class int64{ //万进制高精 
public:
	int len,num[1001];
	int64(){
		memset(num,0,sizeof(num));
		len=0;
	}
	bool operator>(const int64 a)const{
		for(int i=len-1;i>=0;i--)
		{
			if(a.num[i]!=num[i])
			return num[i]>a.num[i];
		}
		return false;
	}
	int64 operator*(const int a)const{
		int64 res=*this;
		for(int i=0;i<len;i++) res.num[i]*=a;
		for(int i=0;i<res.len;i++)
		{
			if(res.num[i]>=10000)
			{
				res.num[i+1]+=res.num[i]/10000;
				res.num[i]%=10000;
			}
		}
		if(res.num[res.len]) res.len++;
		return res;
	}
	int64 operator/(const int a)const{
		int64 res=*this;
		int i;
		for(i=res.len-1;i>=0;i--)
		{
			if(i>0)	res.num[i-1]+=(res.num[i]%a)*10000;
			res.num[i]/=a;
		}
		while(res.len>0 && res.num[res.len-1]==0) res.len--;
		if(res.len==0) res.len=1;
		return res;
	}
	void print(){
		printf("%d",num[len-1]);
		for(int j=len-2;j>=0;j--)
			printf("%04d",num[j]);
		printf("\n");
	}
} s[Maxn]; //前缀和

struct number{
	long long x,y; //正如题意所述 A[i]=pow(10,a[i])
	bool operator<(const number a)const{
		return (x+y)<(a.x+a.y);
	}
} V[Maxn]={0};

int64 Max(int64 x,int64 y)
{
	if(x>y) return x;
	return y;
}

void work()
{
	int64 Ans;
	sort(V+2,V+n+2); //从小到大排序
	s[1].num[0]=V[1].x;
	s[1].len=1; //国王设定 
	for(int i=2;i<=n+1;i++) //计算最大 
	{
		s[i]=s[i-1]*V[i].x;
		if((s[i-1]/V[i].y)>Ans)
			Ans=(s[i-1]/V[i].y);
	}
	Ans.print();
}

void init()
{
	int x,y;
	ios::sync_with_stdio(false); //清除缓存 
	cin>>n;
	for(int i=1;i<=n+1;i++) //0为国王，0-1=-1，不用考虑 
	{
		cin>>V[i].x>>V[i].y;
	}
}

int main()
{
	freopen("kinggame.in","r",stdin);
	freopen("kinggame.out","w",stdout);
	init();
	work();
	return 0;
}
/*
3
1 1
2 3
7 4
4 6
*/