問題一覧 > 通常問題

No.1450 nahco314's First Problem

レベル : / AI推定難易度 : 925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 113
作問者 : NaHCO314 / テスター : shiomusubi496
お気に入りにしたユーザー ProblemId : 6089 / 自分の提出
問題文最終更新日: 2021-03-31 13:16:21
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
新入生プログラミングコンテスト 2021(昼の部) (順位表) の他の問題:

Problem Statement

For a positive integer $N$, let $M$ be the Hamming weight of $N$. Does there exist an $N$ such that $N\oplus M=X$?

Let us state this rigorously.

The Hamming weight is the total number of set bits when an integer is written in binary.
For example, $5$ is written in binary as $101$, in which $1$ appears $2$ times. Therefore, the Hamming weight of $5$ is $2$.

Also, here $A\oplus B$ denotes the bitwise exclusive OR of $A$ and $B$.

You are given a non-negative integer $X$. For a positive integer $N$ and its Hamming weight $M$, determine whether there exists an $N$ such that $N\oplus M$ equals $X$, and if one exists, show $1$ possible value of $N$.

Here, $1\leq N\leq 2\times 10^{18}$ must hold. Under these constraints, it can be proved that if there exists an $N$ satisfying $N\oplus M=X$, then there also exists an $N$ that satisfies $1\leq N\leq 2\times 10^{18}$.

Input

$X$
  • $0\leq X\leq 10^{18}$
  • $X$ is an integer

Output

  • When $M$ is the Hamming weight of $N$, $N\oplus M=X$
  • $1\leq N\leq 2\times 10^{18}$

If there is no $N$ satisfying the above $2$ conditions, print $-1$.

If there exists an $N$ satisfying the conditions, print $1$ possible value of $N$.

If multiple $N$ satisfy the conditions, you may print any of them.

Sample

Sample 1
Input
3
Output
2

When $N=2$, the Hamming weight of $2$ is $1$, so $M=1$, and $N\oplus M=3$.

Sample 2
Input
15
Output
-1

There is no $N$ such that $N\oplus M=15$.

Sample 3
Input
314159265358979
Output
314159265359001

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