No.262 Boring Bit Sugoroku
タグ : / 解いたユーザー数 46
作問者 :
LayCurse
Problem Statement
Carol is about to play a special game of sugoroku.
There are $N$ squares arranged in a straight line, numbered from $1$ to $N$.
The square $1$ is the starting square, and the goal is the square on which $N$ is written.
From the current square, you can move "forward" by the number of $1$ bits in the binary representation of the number written on that square.
(You cannot move to a square numbered less than $1$ or to a square numbered $N+1$ or greater, and you cannot reach the goal unless you land exactly on $N$.)
Given a positive integer $N$, find the minimum number of moves needed to reach the goal (the arrival at the starting square also counts as a move).
If the goal cannot be reached, output $\verb|-1|$.
Input
$N$
$1 \leq N \leq 10^{12}$
Output
Output the minimum number of moves, or $\verb|-1|$.
Sample
Sample 1
Input
3
Output
3
Sample 2
Input
71623783
Output
5691592
Sample 3
Input
1000000000000
Output
-1
For example, when $N$ is sufficiently large, the only way to proceed is as follows.
移動数 1 2 3 4 5 6 7 8 9 ... マス 1 2 3 5 7 10 12 14 17 ...
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。