No.3023 Utility is Max?
Notice
The problem statement was changed at 1:03 (JST) on February 17.
Problem Statement
S has decided to eat "spring roll rice" and "fried rice" for lunch, and K goes out to buy them once a day.
In the Netherworld where they live, there are only two shops selling these items: shop $1$ and shop $2$. The prices at these shops may differ.
On day $i$, K tells S the following information. However, K can visit only one of the two shops per day, and does not tell S at which shop the purchase will be made.
- The price per unit ${A_i}_j$ of "spring roll rice" and the price per unit ${B_i}_j$ of "fried rice" at shop $j$ on that day
- The budget $I_i$ for that day
Here, S's preference for the consumption amount $x (> 0)$ of "spring roll rice" and the consumption amount $y (>0)$ of "fried rice" is defined for each day as a function $f_i(x, y)$ satisfying the following condition, and it is not given in the input.
- For positive real numbers $x, y$, when either one of the values is varied, $f_i(x, y)$ is strictly monotonically increasing.
That is, for all pairs $(x_1, x_2)$ with $0< x_1 < x_2$ and any $y > 0$, we have $f_i(x_1, y) < f_i(x_2, y)$, and
for all pairs $(y_1, y_2)$ with $ 0 < y_1 < y_2$ and any $x > 0$, we have $f_i(x, y_1) < f_i(x, y_2)$.
S may be scatterbrained, and sometimes specifies amounts that cannot be bought with the budget in the first place, or specifies affordable consumption amounts that do not maximize the satisfaction.
On behalf of the busy K, determine for each of the $Q$ days whether the combination of amounts of "spring roll rice" and "fried rice" ${X_i}_j, {Y_i}_j (i=1,2,…,Q, j=1,2)$ can be optimal.
Here, the combination of consumption amounts ${X_i}_j, {Y_i}_j$ specified for day $i$ can be optimal if it satisfies the following conditions.
-
Whichever shop K visits on day $i$, the specified amounts can be purchased within the budget.
That is, for the pairs of amounts to buy ${X_i}_j, {Y_i}_j$, we have ${A_i}_j × {X_i}_j + {B_i}_j × {Y_i}_j ≤ I_i (j = 1,2)$. -
Depending on S's preference on day $i$, whichever shop is visited on day $i$, the specified amounts can achieve the maximum satisfaction at that shop.
That is, for the specified amounts $({X_i}_1, {Y_i}_1,{X_i}_2, {Y_i}_2)$, there exists a preference $f_i(x, y)$ satisfying the following.- For both $j = 1, 2$, the following holds.
- For any pair of positive real numbers $(x, y)$ with ${A_i}_j × x + {B_i}_j × y ≤ I_i$, we have $f_i(x, y) ≤ f_i({X_i}_j, {Y_i}_j)$.
Input
$Q$
$I_1$
${A_1}_1\ {B_1}_1\ {X_1}_1\ {Y_1}_1$
${A_1}_2\ {B_1}_2\ {X_1}_2\ {Y_1}_2$
$I_2$
${A_2}_1\ {B_2}_1\ {X_2}_1\ {Y_2}_1$
${A_2}_2\ {B_2}_2\ {X_2}_2\ {Y_2}_2$
$…$
$I_Q$
${A_Q}_1\ {B_Q}_1\ {X_Q}_1\ {Y_Q}_1$
${A_Q}_2\ {B_Q}_2\ {X_Q}_2\ {Y_Q}_2$
- $1 ≤ Q ≤ 10^5$
- $1 ≤ I_i, {A_i}_j, {B_i}_j, {X_i}_j, {Y_i}_j ≤ 10^9$
- All inputs are integers.
Output
Output Yes if the specification for day $i$ can be optimal, and No if it cannot. Output the answer for day $i$ on line $i$. Print a newline at the end.
Sample
Sample 1
Input
4 10 2 3 2 2 1 4 6 1 12 6 6 100 100 13 1 1 1 1000000000 1 1 1 1 2 1 2 3 29 2 5 2 5 7 1 4 1
Output
Yes No No No
For example, on day 1 the prices of "spring roll rice" and "fried rice" are (2, 3) and (1, 4) at shops 1 and 2, respectively. With this specification, there exists a preference that maximizes the satisfaction at each shop, so output Yes. On day 2, the specification cannot be purchased in the first place, so output No.
Sample 2
Input
1 1000000000 1 10 999999990 1 10 1 1 999999990
Output
Yes
That really is too many carbs. What an appetite.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。