問題一覧 > 通常問題

No.1987 Sandglass Inconvenience

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 120
作問者 : rianoriano / テスター : NatsubiSoganNatsubiSogan milkcoffeemilkcoffee tokusakuraitokusakurai
1 ProblemId : 7411 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-05 23:21:18

問題文

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