No.1450 nahco314's First Problem
タグ : / 解いたユーザー数 113
作問者 :
shiomusubi496
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もしくは右上の雲マークをクリックしてアカウントを作成してください。