No.1987 Sandglass Inconvenience
タグ : / 解いたユーザー数 139
作問者 :
riano
/ テスター :
NatsubiSogan
tokusakurai
milkcoffee
問題文
あなたは $3$ つの砂時計を持っており、それぞれ $a$ 秒、$b$ 秒、$c$ 秒で全ての砂が落ちます。 これらを使って、ちょうど $X$ 秒を測ることができるでしょうか。 ただし、ちょうど $X$ 秒を測ることができるまでに準備が必要な場合は、いくら時間をかけて準備してもよいものとします。
厳密なルールを以下に記します。
- はじめ全ての砂時計について、砂は完全に落ち切っている。
- 砂時計はどちらかを上向きにして置くことができ、上側に砂がある限り均等なペースで砂が落ち続ける。
- あなたは最初にいくつかの砂時計を選んでひっくり返した後、「いずれかの砂時計の砂が落ち切った瞬間」に任意の砂時計の状態を変える操作をすることができる。特に、砂が落ちている途中の他の砂時計をひっくり返してもよい。
- その際操作にかかる時間は無視でき、また同時刻に複数の砂時計を操作してよい。
- ちょうど $X$ 秒測れたとは、「ある操作または砂が落ち切ったタイミング」から「別の操作または砂が落ち切ったタイミング」までの間隔がちょうど $X$ 秒になることを言う。
入力
$a\ \ b\ \ c$ $X$
- $1\leq a,b,c,X\leq 10^{12}$
- 入力は全て整数である
出力
ちょうど $X$ 秒を測ることが可能であれば Yes を、不可能であれば No を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 10 15 1
出力
Yes
はじめに、$10$ 秒の砂時計と $15$ 秒の砂時計をひっくり返します。$10$ 秒後、片方の砂時計の砂が落ち切りますので、この瞬間に $6$ 秒の砂時計をひっくり返します。 すると、最初に砂時計をひっくり返したタイミングからちょうど $15$ 秒後に $15$ 秒の砂時計の、 $16$ 秒後に $6$ 秒の砂時計の砂が落ち切ります。 この間隔はちょうど $1$ 秒であるため、測ることができています。
サンプル2
入力
1000000000000 999999999995 2 5
出力
Yes$1000000000000(=10^{12})$ 秒の砂時計と $999999999995(=10^{12}-5)$ 秒の砂時計を同時にひっくり返します。 この $2$ つの砂時計の砂が落ち切るタイミングはちょうど $5$ 秒差ですので、これで測ることができます。 この際、$5$ 秒を測れるまでに長い時間がかかっていますが、このようなことは許容されます。
サンプル3
入力
1000000000000 100000000000 1000000000000 20
出力
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。