/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 2400 点
問題文
砂時計が 2 つあり、一方は 1 秒計、もう一方は \sqrt{2} 秒計です。 これで x + y \sqrt{2} 秒を測ることは可能でしょうか。
厳密に述べましょう。 2 つの砂時計 A, B があり、各砂時計には砂が入る 2 つの「球」があります。 各砂時計は、縦か横に置くことができます。 縦に置くと、上の球が砂を含む限り、砂が下の球に 1 秒あたり 1 グラムの速さで流れ続けます。 横に置くと、砂は流れません。 縦に置く方法はどちらの球が上になるかで 2 通りあるため、各砂時計は合計で 3 通りの状態のいずれかにあります。
砂時計 A に含まれる砂の量は 1 グラム、砂時計 B に含まれる砂の量は \sqrt{2} グラムです。したがって、砂時計 A が縦に置かれ、砂が全て上の球にあるとき、砂が下の球に落ち切るまでに 1 秒を要します。 同様に、砂時計 B はこれに \sqrt{2} 秒を要します。
はじめ、砂時計 A, B はともに縦に置かれており、砂は全て下の球にあります。 すぬけ君が叫ぶまでは、何にも触れてはいけません。 すぬけ君の叫びからちょうど t 秒後に 出来事 (後述) が起こったとき、t 秒を測れたといいます。
出来事 が起こったとは、以下のいずれかが起こったことをいいます。
- すぬけ君が叫んだ。
- 縦に置かれた砂時計の砂がちょうど落ち切った。
出来事 が起こったとき、次の操作を (何度でも) 無視できる時間で行えます。
- 砂時計を 1 つ選び、それを別の状態にする。
例えば、以下のようにして -1 + 2 \sqrt{2} 秒を測れます。
- 時刻 0 に、すぬけ君が叫ぶ。A, B をともにひっくり返す。
- 時刻 1 に、A の砂が落ち切る、という出来事が起こる。A を再びひっくり返す (B はそのまま)。
- 時刻 \sqrt{2} に、B の砂が落ち切る、という出来事が起こる。A を再びひっくり返し、B は横にしておく。
- 時刻 -1 + 2 \sqrt{2} に、A の砂が落ち切る、という出来事が起こる。
x_i + y_i \sqrt{2} という形の数が Q 個与えられるので、それぞれについて上記の問題を解いてください。
制約
- 1 \leq Q \leq 10^5
- -10^9 \leq x_i, y_i \leq 10^9
- x_i + y_i \sqrt{2} > 0
- 入力中の全ての値は整数である。
入力
入力は標準入力から以下の形式で与えられる。
Q x_1 y_1 : x_Q y_Q
出力
Q 行出力せよ。
出力の i 行目は、x_i + y_i \sqrt{2} 秒を測ることが可能なら Yes、不可能なら No とすること。
入力例 1
3 -1 2 2020 1227 2 -1
出力例 1
Yes Yes No
Score : 2400 points
Problem Statement
You have two sandglasses: a sandglass that can measure 1 second, and a sandglass that can measure \sqrt{2} seconds. Is it possible to measure x + y \sqrt{2} seconds using them?
Let's formalize the statement. We have two sandglasses named A and B. Each sandglass has two bulbs, and the bulbs may contain sand. We can place each sandglass in one of the three states: two vertical states (one of the bulbs is placed on top of the other, and in case the top bulb contains sand, the sand in the top bulb keeps falling into the bottom bulb at the speed of one gram per second.) and one horizontal state (the sand does not move.)
The sandglass A contains 1 gram of sand and the sandglass B contains \sqrt{2} grams of sand. Thus, when sandglass A is vertically placed and all sand is in the top bulb, it takes 1 second until all sand falls into the bottom bulb. Similarly, this time is \sqrt{2} seconds for sandglass B.
Initially, both A and B are vertically placed, and all sand is in the bottom bulb. You are not allowed to touch anything before Snuke shouts. When an event (described below) happens exactly t seconds after Snuke shouts, we say that we can measure t seconds.
We say that an event happens when one of the following happens:
- Snuke shouts.
- The sand in a sandglass in a vertical state has just stopped falling down.
When an event happens, we can perform (an arbitrary number of) the following operation in negligible time:
- Choose a sandglasses, and change its state.
For example, we can measure -1 + 2 \sqrt{2} seconds as follows:
- At time 0, Snuke shouts. Turn both A and B upside down.
- At time 1, an event happens: the sand in A stops falling down. Turn A upside down again (and leave B as it is).
- At time \sqrt{2}, an event happens: the sand in B stops falling down. Turn A upside down again, and leave B in the horizontal state.
- At time -1 + 2 \sqrt{2}, an event happens: the sand in A stops falling down.
You are given Q numbers of the form x_i + y_i \sqrt{2}. Solve the problem above for each given number.
Constraints
- 1 \leq Q \leq 10^5
- -10^9 \leq x_i, y_i \leq 10^9
- x_i + y_i \sqrt{2} > 0
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
Q x_1 y_1 : x_Q y_Q
Output
Print Q lines.
On the i-th line, print Yes if it is possible to measure x_i + y_i \sqrt{2} seconds; otherwise print No.
Sample Input 1
3 -1 2 2020 1227 2 -1
Sample Output 1
Yes Yes No