[NOIP2012 提高组] 国王游戏
典贪心。设当前点为 \(i\)，\(\prod_{k=0}^{i-1}a_k\) 为 \(x\)，则对于 \(i,j\) 两点的答案：（为了方便，记 \(i+1=j\)）
\[\mathit{res}_1=\max\bigg(\dfrac x{b_i},\dfrac{xa_i}{b_j}\bigg)~; \]若交换，则：
\[\mathit{res}_2=\max\bigg(\dfrac x{b_j},\dfrac{xa_j}{b_i}\bigg)~. \]假设不交换更大，则：
\[\max\bigg(\dfrac x{b_i},\dfrac{xa_i}{b_j}\bigg)>\max\bigg(\dfrac x{b_j},\dfrac{xa_j}{b_i}\bigg) \]显然两个 \(\max\) 满足对称性，不妨设 \(\dfrac x{b_i}<\dfrac{xa_i}{b_j}\)。又因为都是正整数，所以 \(\dfrac{xa_i}{b_j}>\dfrac x{b_j}\)。那么使该式成立当且仅当
\[\dfrac{xa_i}{b_j}>\dfrac{xa_j}{b_i}~. \]消去 \(x\)，移项，就得到：
\[a_ib_i>a_jb_j~. \]因为国王要求答案最小，所以按照 \(a_ib_i<a_jb_j\) 来排序之后统计答案即可。
高精度去死！
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
constexpr int MAXN=1005;
int n;
struct P{
int a,b;
bool operator<(const P&x)const{
return a*b<x.a*x.b;
}
}p[MAXN];
struct BIG{
int s[MAXN<<2],len;
BIG(){
memset(s,0,sizeof(s));
len=0;
}
BIG operator=(int x){
BIG res;
do res.s[++res.len]=x%10,x/=10;while(x);
return *this=res;
}
BIG(int x){
*this=x;
}
bool operator<(const BIG&x)const{
if(len^x.len) return len<x.len;
for(int i=x.len;i;--i)
if(s[i]^x.s[i])
return s[i]<x.s[i];
return 0;
}
void upd(){
while(len>1&&!s[len]) --len;
}
BIG operator*(const BIG&x)const{
BIG res;
int l=len+x.len;
for(int i=1;i<=len;++i)
for(int j=1;j<=x.len;++j)
res.s[i+j-1]+=s[i]*x.s[j];
for(int i=1;i<=l;++i)
if(res.s[i]>9)
res.s[i+1]+=res.s[i]/10,res.s[i]%=10;
res.len=l,res.upd();
return res;
}
BIG operator/(const int&x)const{
BIG res;
int tmp=0,l=len;
for(int i=l;i;--i){
tmp=(tmp<<3)+(tmp<<1)+s[i];
while(tmp>=x) res.s[i]+=tmp/x,tmp%=x;
}
res.len=l,res.upd();
return res;
}
void write(){
for(int i=len;i;--i) putchar(s[i]+48);
putchar('\n');
}
};
int main(){
n=read();
for(int i=0;i<=n;++i) p[i]={read(),read()};
sort(p+1,p+n+1);
BIG res=0,lhs=p[0].a;
for(int i=1;i<=n;++i){
res=max(res,lhs/p[i].b);
lhs=lhs*p[i].a;
}
res.write();
return fw,0;
}