問題一覧 > 通常問題

No.3023 Utility is Max?

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : 👑 ArcAki / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11548 / 自分の提出
問題文最終更新日: 2025-02-17 01:02:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 456 オムニバス (順位表) の他の問題:

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
After hearing this information, S instructs K to buy ${X_i}_j, {Y_i}_j (j=1, 2)$ of "spring roll rice" and "fried rice", respectively, in the case of buying at shop $j$.
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's satisfaction is defined as $f_i(X, Y)$, where $X, Y$ are the consumption amounts of "spring roll rice" and "fried rice", respectively.
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)$.
    Here, ${X_i}_j, {Y_i}_j$ are given as positive integers in the input, but for $x, y$ all combinations of positive real numbers, not necessarily integers, are considered.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。