[NOIP 2012 提高组] 国王游戏

Luogu
IDLGP1080
Time1000ms
Memory125MB
DifficultyP5
贪心高精度2012NOIP 提高组排序
恰逢 H 国国庆,国王邀请 $n$ 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 $n$ 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。 ## Input 第一行包含一个整数 $n$,表示大臣的人数。 第二行包含两个整数 $a$ 和 $b$,之间用一个空格隔开,分别表示国王左手和右手上的整数。 接下来 $n$ 行,每行包含两个整数 $a$ 和 $b$,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。 ## Output 一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。 [samples] ## Note **【输入输出样例说明】** 按 $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 \le n \le 10,0 < a,b < 8$; 对于 $40\%$ 的数据,有 $1 \le n \le 20,0 < a,b < 8$; 对于 $60\%$ 的数据,有 $1 \le n \le 100$; 对于 $60\%$ 的数据,保证答案不超过 $10^9$; 对于 $100\%$ 的数据,有 $1 \le n \le 1000,0 < a,b < 10000$。 NOIP 2012 提高组 第一天 第二题。
Samples
Input #1
3 
1 1 
2 3 
7 4 
4 6 
Output #1
2
API Response (JSON)
{
  "problem": {
    "name": "[NOIP 2012 提高组] 国王游戏",
    "description": {
      "content": "恰逢 H 国国庆,国王邀请 $n$ 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 $n$ 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。 国王不希望某一个大臣获得特别多",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 128000
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP1080"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "恰逢 H 国国庆,国王邀请 $n$ 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 $n$ 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。\n\n国王不希望某一个大臣获得特别多...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments