B - rng

Contest Duration: 2018-07-14(Sat) 12:00 - 2018-07-14(Sat) 14:30 (local time) (150 minutes) Back to Home

B - rng_10s Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

コンビニエンスストアのりんごマートでは，りんごジュースを販売しています。

りんごマートはある日の朝に開店し，その時にはジュースの在庫が $A$ 本ありました。すぬけ君は毎日昼にりんごマートでジュースを $B$ 本買います。りんごマートでは毎日夜にジュースの在庫を確認し， $C$ 本以下だった場合，次の日の朝までに $D$ 本在庫を追加します。

すぬけ君がジュースを永遠に買い続けられるかを判定して下さい。つまり，ジュースを買おうとした時，必ず在庫が $B$ 本以上あるかどうかを判定して下さい。すぬけ君以外がジュースを買うことはありません。

また，今回の問題では入力ケースは $T$ 個のクエリからなります。

制約

$1 \leq T \leq 300$
$1 \leq A, B, C, D \leq 10^{18}$
入力される値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

 $T$ 
 $A_1$   $B_1$   $C_1$   $D_1$ 
 $A_2$   $B_2$   $C_2$   $D_2$ 
 $:$ 
 $A_T$   $B_T$   $C_T$   $D_T$

$i$ 個目のクエリにおいては， $A = A_i, B = B_i, C = C_i, D = D_i$ である。

出力

$T$ 行出力せよ。 $i$ 行目には， $i$ 個目のクエリですぬけ君が永遠にりんごジュースを買い続けられる場合 Yes，そうでない場合 No と出力せよ。

入力例 1Copy

Copy

14
9 7 5 9
9 7 6 9
14 10 7 12
14 10 8 12
14 10 9 12
14 10 7 11
14 10 8 11
14 10 9 11
9 10 5 10
10 10 5 10
11 10 5 10
16 10 5 10
1000000000000000000 17 14 999999999999999985
1000000000000000000 17 15 999999999999999985

出力例 1Copy

Copy

No
Yes
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
No
Yes

$1$ 個目のクエリでは在庫の個数は以下のように変動します。

$9$ →昼 $2$ →夜 $11$ →昼 $4$ →夜 $13$ →昼 $6$ →夜 $6$ →昼 x

$2$ 個目のクエリでは在庫の個数は以下のように変動します。

$9$ →昼 $2$ →夜 $11$ →昼 $4$ →夜 $13$ →昼 $6$ →夜 $15$ →昼 $8$ →夜 $8$ →昼 $1$ →夜 $10$ →昼 $3$ →夜 $12$ →昼 $5$ →夜 $14$ →昼 $7$ →夜 $7$ →昼 $0$ →夜 $9$ →昼 $2$ →夜 $11$ →昼 …

と続いていき，このまま永遠に購入し続けられます。

入力例 2Copy

Copy

出力例 2Copy

Copy

No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No

Score : $600$ points

Problem Statement

Ringo Mart, a convenience store, sells apple juice.

On the opening day of Ringo Mart, there were $A$ cans of juice in stock in the morning. Snuke buys $B$ cans of juice here every day in the daytime. Then, the manager checks the number of cans of juice remaining in stock every night. If there are $C$ or less cans, $D$ new cans will be added to the stock by the next morning.

Determine if Snuke can buy juice indefinitely, that is, there is always $B$ or more cans of juice in stock when he attempts to buy them. Nobody besides Snuke buy juice at this store.

Note that each test case in this problem consists of $T$ queries.

Constraints

$1 \leq T \leq 300$
$1 \leq A, B, C, D \leq 10^{18}$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $T$ 
 $A_1$   $B_1$   $C_1$   $D_1$ 
 $A_2$   $B_2$   $C_2$   $D_2$ 
 $:$ 
 $A_T$   $B_T$   $C_T$   $D_T$

In the $i$ -th query, $A = A_i, B = B_i, C = C_i, D = D_i$ .

Output

Print $T$ lines. The $i$ -th line should contain Yes if Snuke can buy apple juice indefinitely in the $i$ -th query; No otherwise.

Sample Input 1Copy

Copy

14
9 7 5 9
9 7 6 9
14 10 7 12
14 10 8 12
14 10 9 12
14 10 7 11
14 10 8 11
14 10 9 11
9 10 5 10
10 10 5 10
11 10 5 10
16 10 5 10
1000000000000000000 17 14 999999999999999985
1000000000000000000 17 15 999999999999999985

Sample Output 1Copy

Copy

No
Yes
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
No
Yes

In the first query, the number of cans of juice in stock changes as follows: (D represents daytime and N represents night.)

$9$ →D $2$ →N $11$ →D $4$ →N $13$ →D $6$ →N $6$ →D x

In the second query, the number of cans of juice in stock changes as follows:

$9$ →D $2$ →N $11$ →D $4$ →N $13$ →D $6$ →N $15$ →D $8$ →N $8$ →D $1$ →N $10$ →D $3$ →N $12$ →D $5$ →N $14$ →D $7$ →N $7$ →D $0$ →N $9$ →D $2$ →N $11$ →D …

and so on, thus Snuke can buy juice indefinitely.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No