记录编号	50485	评测结果	EEEEEEEEEE
题目名称	[NOIP 2012]国王游戏	最终得分	0
用户昵称	cqw	是否通过	未通过
代码语言	C++	运行时间	0.718 s
提交时间	2012-11-23 10:00:46	内存使用	0.32 MiB

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
struct node
{
	int a,b;
}D[1005],K;
int cmp(const void* a,const void* b)
{
	node *p=(node*)a;
	node *q=(node*)b;
	int max1,max2;
	max1=max(q->b,p->b*q->a);
	max2=max(p->b,q->b*p->a);
	if(max1==max2) return p->a-q->a;
	return max1-max2;
}
int ans;
int Count=0;
int used[1005];
void dfs(int mul,int d,int n,int val)
{
	if(val>ans) return ;
	if(d==n)
	{
		ans=val;
		return ;
	}
	if(++Count>100000) return;
	for(int i=0;i<n;i++)
	{
		if(!used[i])
		{
			used[i]=1;
			dfs(mul*D[i].a,d+1,n,max(val,mul/D[i].b));
			used[i]=0;
		}
	}
}
int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	int n;
	scanf("%d",&n);
	scanf("%d%d",&K.a,&K.b);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&D[i].a,&D[i].b);
		used[i]=0;
	}
	qsort(D,n,sizeof(node),cmp);
	ans=0;
	int mul=1;
	for(int i=0;i<n;i++)
	{
		int k=mul*K.a/D[i].b;
		if(ans<(mul*K.a)/D[i].b) ans=(mul*K.a)/D[i].b;
		mul*=D[i].b;
	}
	Count=0;
	dfs(K.a,0,n,0);
	printf("%d\n",ans);
}