問題一覧 > 通常問題

No.1450 nahco314's First Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 71
作問者 : NaHCO3_314NaHCO3_314 / テスター : shiomusubi496shiomusubi496
7 ProblemId : 6089 / 出題時の順位表
問題文最終更新日: 2021-03-31 13:16:21

問題文

正整数 $N$ について $M$ を $N$ のハミング重みとしたとき、 $N\oplus M=X$ となるような $N$ は存在するでしょうか。

厳密に述べましょう。

ハミング重みとは、整数を二進数表記にしたときに立っているビットの総数のことです。
例えば、 $5$ を二進数で表すと $101$ で、 $1$ が $2$ つあります。よって、 $5$ のハミング重みは $2$ となります。

また、ここで $A\oplus B$ は $A$ と $B$ のビットごとの排他的論理和を表します。

非負整数 $X$ が与えられます。正整数 $N$ とそのハミング重み $M$ に関して、 $N\oplus M$ が $X$ となる $N$ が存在するかを判定し、存在する場合は $N$ として考えられるものを $1$ つ示してください。

ただし、 $1\leq N\leq 2\times 10^{18}$ である必要があり、この制約下では $N\oplus M=X$ を満たす $N$ が存在する場合 $1\leq N\leq 2\times 10^{18}$ も満たす $N$ が存在することが証明できます。

入力

$X$
  • $0\leq X\leq 10^{18}$
  • $X$ は整数

出力

  • $N$ のハミング重みを $M$ としたときに $N\oplus M=X$
  • $1\leq N\leq 2\times 10^{18}$

上記 $2$ つの条件を満たす $N$ が存在しない場合 $-1$ と出力してください。

条件を満たす $N$ が存在する場合、 $N$ として考えられるものを $1$ つ出力してください。

条件を満たす $N$ が複数存在する場合、そのうちどれを出力しても構いません。

サンプル

サンプル1
入力
3
出力
2

$N=2$ の時、 $2$ のハミング重みは $1$ なので $M=1$ になり、 $N\oplus M=3$ となります。

サンプル2
入力
15
出力
-1

$N\oplus M=15$ となるような $N$ は存在しません。

サンプル3
入力
314159265358979
出力
314159265359001

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