OpenJudge

02:庆祝运动会

总时间限制:
1000ms
内存限制:
65536kB
描述

某校刚刚举办了运动会,某班为了庆祝取得的优异成绩,班长邀请n位同学来玩一个有奖游戏。首先,他让每个同学在左、右手上面分别写下一个整数,班长自己也在左、右手上各写一个整数。然后,让这n 位同学排成一排,班长站在队伍的最前面。排好队后,所有的同学都会获得班长奖赏的若干金币,每位同学获得的金币数分别是:排在该同学前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。 班长不希望某一个同学获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序, 使获得奖赏最多的同学,所获奖赏尽可能的少。注意,班长的位置始终在队伍的最前面。

输入
第一行包含一个整数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%的数据,保证答案不超过 10^9;
对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。
全局题号
17028
添加于
2018-04-14
提交次数
161
尝试人数
31
通过人数
11