問題一覧 > 通常問題

No.680 作れる数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : tailstails / テスター : はむこはむこ
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 \le N \le 1000000000=10^9$
$N$ は整数です。

出力

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

サンプル

サンプル1
入力
10
出力
YES

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

サンプル2
入力
12
出力
NO

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

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