Description：

所有人站成一排，每个人获得的钱为排在他前面的所有人的左手上的数的乘积除以他自己右手上的数，问怎样安排使得获得的钱最多的人获得的钱最少。

$1\le n \le 1000$

Solution：

设两个相邻的人 $a$ 和 $b$ ， $a$ 前所有人左手上的数乘积为 $S$ ，那么第一个人获得的钱为 $S/r_a$ ，第二个人获得的钱为 $S\times l_a/r_b$ ，那么不交换的前提就是 $\max(S/r_a,S\times l_a/r_b)<\max(S/r_b,S\times l_b/r_a)$ ，这个条件等价于 $S\times l_a/r_b<S\times l_b/r_a$ ，也就是 $l_a\times r_a<l_b\times r_b$ ，按 $l\times r$ 为关键字排序就好。

要写高精。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n;

#define MAXN 1010

struct peo

{

	int l,r;

}s[MAXN];

bool cmp_mul(peo a,peo b){return a.l * a.r < b.l * b.r;}

struct bigint

{

	int len,m[10000];

	bigint(){len = 0;memset(m,0,sizeof(m));}

	void set1()

	{

		m[1] = 1;

		len = 1;

		return;

	}

	friend bigint operator * (bigint a,int b)

	{

		for(register int i = 1;i <= a.len;++i)

			a.m[i] *= b;

		for(register int i = 1;i <= a.len;++i)

		{

			a.m[i + 1] += a.m[i] / 10;

			a.m[i] %= 10;

		}

		while(a.m[a.len + 1] != 0)

		{

			++a.len;

			a.m[a.len + 1] += a.m[a.len] / 10;

			a.m[a.len] %= 10;

		}

		return a;

	}

	friend bigint operator / (bigint a,int b)

	{

		register bigint res;

		register int tmp = 0;

		register int l = 0;

		for(register int i = a.len;i >= 1;--i)

		{

			tmp = tmp * 10 + a.m[i];

			if(tmp >= b)

			{

				res.m[i] = tmp / b;

				l = max(l,i);

				tmp -= tmp / b * b;

			}

		}

		res.len = l;

		return res;

	}

	inline void print()

	{

	    if(len == 0)

	    {

	        puts("0");

	        return;

	    }

		for(register int i = len;i >= 1;--i)printf("%d",m[i]);

		puts("");

		return;

	}

	bool operator < (const bigint b)const

	{

	    if(len < b.len)return true;

	    if(len > b.len)return false;

	    for(int i = len;i >= 1;--i)

	    {

	        if(m[i] < b.m[i])return true;

	        if(m[i] > b.m[i])return false;

	    }

	    return false;

	}

};

int main()

{

	scanf("%d",&n);

	int a,b;

	scanf("%d%d",&a,&b);

	for(int i = 1;i <= n;++i)

	{

		s[i].l = read();s[i].r = read();

	}

	sort(s + 1,s + 1 + n,cmp_mul);

	register bigint res;res.set1();

	res = res * a;

	register bigint ans;

	for(register int i = 1;i <= n;++i)

	{

	    ans = max(ans,res / s[i].r);

	    res = res * s[i].l;

	}

	ans.print();

	return 0;

}