問題一覧 > 通常問題

No.2063 ±2^k operations (easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 175
作問者 : とりゐ / テスター : 👑 qand ygussany karinohito
お気に入りにしたユーザー ProblemId : 8446 / 自分の提出
問題文最終更新日: 2022-09-01 01:31:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 359 (順位表) の他の問題:

Problem Statement

Let $n$ be a positive integer. Starting from $X=n$, let $f(n)$ be the minimum number of operations required to make $X=0$ by repeating the following operation.

  • Choose a non-negative integer $k$ and one of the operators $+,-$.
    • If the operator is $+$, replace $X$ with $X+2^k$.
    • If the operator is $-$, replace $X$ with $X-2^k$.
A positive integer $N$ is given in base $2$. Determine whether $f(N)=2$.

Input

$N$

  • $1\leq N\lt 2^{100000}$
  • $N$ is given in base $2$.

Output

If $f(N)=2$, print Yes; otherwise, print No.

Sample

Sample 1
Input
10100
Output
Yes

Since $N$ is given in base $2$, converting it to base $10$ gives $N=20$.

For $n=20$, choosing $(2,-)$ in operation number $1$ makes $X=16$, and choosing $(4,-)$ in operation number $2$ makes $X=0$. Since it is impossible to reach $0$ with $1$ operation, $f(20)=2$.

Sample 2
Input
11100
Output
Yes

Since $N$ is given in base $2$, converting it to base $10$ gives $N=28$.

For $n=28$, choosing $(5,-)$ in operation number $1$ makes $X=-4$, and choosing $(2,+)$ in operation number $2$ makes $X=0$. Since it is impossible to reach $0$ with $1$ operation, $f(28)=2$.

Sample 3
Input
10000
Output
No

Since $N$ is given in base $2$, converting it to base $10$ gives $N=16$.

For $n=16$, choosing $(4,-)$ in operation number $1$ makes $X=0$. Thus, $f(16)=1$.

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