记录编号	321686	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]国王游戏	最终得分	100
用户昵称	核糖核酸	是否通过	通过
代码语言	C++	运行时间	2.184 s
提交时间	2016-10-13 21:06:23	内存使用	1.13 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 10005
using namespace std;
struct Node {
	int lf, rf;
} p[N];
int n;
struct Bigint {
	int s[100005], len;
	
	void Init() {
		memset(s, 0, sizeof(s));
		len = -1;
	}
	
	void print() {
		for(int i=len; i>=0; i--) putchar(s[i]+'0');
		puts("");
	}
	
	Bigint operator = (int b) {
		Init();
		if(b == 0) len = 0;
		else while(b) {
			s[++len] = b % 10;
			b /= 10;
		}
		return *this;
	}
	
	Bigint operator = (const Bigint & b) {
		Init();
		len = b.len;
		for(int i=0; i<=len; i++) s[i] = b.s[i];
		return *this;
	}
	
	bool operator == (const Bigint & b) const {
		if(len != b.len) return false;
		for(int i=0; i<=len; i++)
			if(s[i] != b.s[i]) return false;
		return true;
	}
	
	bool operator >= (const Bigint & b) const {
		if(*this == b) return true;
		if(len < b.len) return false;
		if(len > b.len) return true;
		for(int i=len; i>=0; i--) {
			if(s[i] > b.s[i]) return true;
			if(s[i] < b.s[i]) return false;
		}
	}
	
	Bigint operator * (const int & b) const {
		Bigint t; t.Init();
		for(int i=0; i<=len; i++)
			t.s[i] += s[i] * b;
		for(int i=0; i<=(len+50); i++) {
			t.s[i+1] += (t.s[i] / 10);
			t.s[i] %= 10;
		}
		t.len = len + 50;
		while(t.len && t.s[t.len]==0) t.len--;
		return t;
	}
	
	Bigint operator / (const int & b) const {
		Bigint t; t.Init();
		int v = 0;
		for(int i=len; i>=0; i--) {
			v = v * 10 + s[i];
			if(v >= b) {
				t.s[i] = v / b;
				v %= b;
			}
		}
		t.len = len;
		while(t.len && t.s[t.len]==0) t.len--;
		return t;
	}
	
};

Bigint sum, ans;

void Solve() {
	ans = 0;
	sum = p[0].lf;
	for(int i=1; i<=n; i++) {
		Bigint sco;
		sco = sum / p[i].rf;
		if(sco >= ans) ans = sco;
		sum = sum * p[i].lf;
	}
	ans.print();
}

bool cmp(const Node aa, const Node bb) {
	return aa.lf * aa.rf < bb.lf * bb.rf;
}

int main() {
	freopen("kinggame.in", "r", stdin);
	freopen("kinggame.out", "w", stdout);

	scanf("%d", &n);
	for(int i=0; i<=n; i++) scanf("%d%d", &p[i].lf, &p[i].rf);
	sort(p+1, p+n+1, cmp);
	Solve();
	
	return 0;
}