No.680 作れる数

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 :

tails / テスター :

はむこ

13 ProblemId : 1776 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2018-01-18 16:59:07

Yukiさんは、次のような「数の作り方」を考えました。

ステップ1: 初期状態として $s = 0, t = 0$ とします。
ステップ2: $t$ の値を2倍し、新たな $t$ の値とします（ $t := t \times 2$ ）。
ステップ3: 心の中でコインをトスします。表が出たら、 $t$ の値に $1$ を加え、新たな $t$ の値とします（ $t := t + 1$ ）。コインの表が出るかどうかは、都合良く決めて構いません。
ステップ4: $s$ の値に $t$ の値を加え、新たな $s$ の値とします（ $s := s + t$ ）。
ステップ5: 心の中でサイコロを振ります。 $1$ 以外の目が出たら、ステップ2に戻ります。サイコロの出目は、都合良く決めて構いません。
ステップ6: 作った数として $s$ の値を出力し、終了します。

さて、整数

N

が与えられたとき、

N

が上記の「数の作り方」で作れるかどうか判定してください。
作れる場合は YES を、作れない場合は NO を出力してください。

$N$

$0 \leq N \leq 1000000000 = 10^{9}$
$N$ は整数です。

YES または NO を出力してください。

YES

$10 = 1 + 3 + 6$ です。なので、ステップ3でうまくコインをトスして、ステップ4のときの $t$ の値が $1, 3, 6$ となるようにすると、 $10$ を作ることができます。

NO

$12$ は、どうやっても作れないようです。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。