P1080 [NOIP 2012 Senior] King's Game

It is the National Day of country H, and the king invites $n$ ministers to play a prize game. First, he asks each minister to write an integer on his left hand and an integer on his right hand; the king also writes one integer on his left hand and one on his right hand. Then the $n$ ministers line up in a row, with the king standing at the very front. After the lineup is fixed, every minister will receive some gold coins from the king. The number of coins a minister receives equals the product of the numbers on the left hands of all people standing before that minister, divided by the integer on his own right hand, and then taking the floor. The king does not want any single minister to get too many coins, so he asks you to rearrange the order of the ministers to make the maximum number of coins received by any minister as small as possible. Note that the king always stands at the very front.

The first line contains an integer $n$, the number of ministers. The second line contains two integers $a$ and $b$ separated by a space, representing the integers on the king’s left and right hands, respectively. Each of the next $n$ lines contains two integers $a$ and $b$ separated by a space, representing one minister’s left- and right-hand integers, respectively.

Output one integer, the maximum number of coins received by any minister in the optimal arrangement.

[Input/Output Sample Explanation] If the lineup is 1, 2, 3, the maximum number of coins received is 2. If the lineup is 1, 3, 2, the maximum number of coins received is 2. If the lineup is 2, 1, 3, the maximum number of coins received is 2. If the lineup is 2, 3, 1, the maximum number of coins received is 9. If the lineup is 3, 1, 2, the maximum number of coins received is 2. If the lineup is 3, 2, 1, the maximum number of coins received is 9. Therefore, the minimum possible maximum is 2, so output 2. Constraints: For 20% of the testdata, $1 \le n \le 10$, $0 < a, b < 8$. For 40% of the testdata, $1 \le n \le 20$, $0 < a, b < 8$. For 60% of the testdata, $1 \le n \le 100$. For 60% of the testdata, it is guaranteed that the answer does not exceed $10^9$. For 100% of the testdata, $1 \le n \le 1000$, $0 < a, b < 10000$. NOIP 2012 Senior, Day 1, Problem 2. Translated by ChatGPT 5