国王的游戏(贪心 模拟 高精)

输入描述:

第一行包含一个整数 n ，表示大臣的人数。
第二行包含两个整数 a 和 b ，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b ，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出描述:

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

3 
1 1 
2 3 
7 4 
4 6

2

按 1 、 2 、 3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ；
按 1 、 3 、 2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ；
按 2 、 1 、 3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ；
按 2 、 3 、 1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9 ；
按 3 、 1 、 2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ；
按 3 、 2 、 1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9 。
因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2 。

备注:

对于 20%的数据，有 1≤ n≤ 10,0 ＜ a,b ＜ 8 ；
对于 40%的数据，有 1≤ n≤20,0 ＜a,b＜8 ；
	

		对于 60%的数据，有 1≤ n≤100 ；
	

	

		对于 60%的数据，保证答案不超过 109 ；
	
对于 100%的数据，有 1 ≤ n ≤1,000,0 ＜ a,b ＜ 10000 。

//国王的游戏(贪心 模拟 高精) 
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;

struct S
{
	int l;
	int r;
};

int n;
S s[N];
int l , r;

bool cmp(S a , S b)
{
	return a.l * a.r < b.l * b.r;
}

vector<int> mult(vector<int> &num , int x)
{
	int t = 0;
	vector<int> ans;
	for(int i = 0 ; i < num.size() || t ; i++)
	{
		if(i < num.size())
			t += num[i] * x;
		ans.push_back(t % 10);
		t /= 10;
	}
	return ans;
}

vector<int> div(vector<int> &num , int x)
{
	int t = 0;
	vector<int> ans;
	for(int i = num.size() - 1 ; i >= 0 ; i--)
	{
		t = t * 10 + num[i];
		ans.push_back(t / x);
		t %= x;	
	}	
	
	reverse(ans.begin() , ans.end());
	while(ans.back() == 0 && ans.size() > 1)
		ans.pop_back();
	return ans;
}

bool operator > (vector<int> &a , vector<int> &b)
{
	if(a.size() != b.size())
		return a.size() > b.size();
	
	for(int i = a.size() - 1 ; i >= 0 ; i--)
	{
		if(a[i] != b[i])
			return a[i] > b[i];
	}
	
	return false;
}

ostream& operator << (ostream &out , vector<int> &num)
{
	for(int i = num.size() - 1 ; i >= 0 ; i--)
		out<<num[i];
	out<<endl;
}

int main()
{
	scanf("%d" , &n);
	scanf("%d %d" , &l , &r);
	for(int i = 0 ; i < n ; i++)
		scanf("%d %d" , &s[i].l , &s[i].r);
	
	sort(s , s + n , cmp);
	
	vector<int>num , ans;
	num.push_back(l);
	for(int i = 0 ; i < n ; i++)
	{	
		vector<int> val = div(num , s[i].r);
		//cout<<num<<val;
		num = mult(num , s[i].l);
			
		if(val > ans || ans.size() == 0)
			ans = val;
	}
	
	for(int i = ans.size() - 1 ; i >= 0 ; i--)
		printf("%d" , ans[i]);
	return 0;
}