No.1286 Stone Skipping
Problem Statement
Koboshi is playing by throwing a stone toward the water surface. Each time the stone flies a distance of $x$ and lands on the water surface, one of the following happens.
- It bounces off the water surface, flies a distance of $\lfloor\frac{x}{2}\rfloor$, and lands on the water surface again.
- It does not bounce off the water surface and sinks on the spot.
You may choose any positive integer as the stone's initial flight distance.
Koboshi wants the total flight distance of the stone to be $D$. What initial flight distance can make the total flight distance equal to $D$? If there are multiple answers, find the smallest one.
Input
$D$
- $1\le D\le 10^{18}$
- $D$ is an integer.
Output
Output the minimum initial flight distance for which the total flight distance of the stone can be $D$.
Sample
Sample 1
Input
10
Output
6
When the initial flight distance is $6$, bouncing makes the stone fly a further $\lfloor\frac{6}{2}\rfloor=3$. Bouncing once more makes it fly a further $\lfloor\frac32\rfloor=1$. If it then sinks, the total flight distance is $10$. When the initial flight distance is less than $6$, the total flight distance cannot be $10$, so the minimum is $6$.
Sample 2
Input
5
Output
5
Set the initial flight distance to $5$, and the stone sinks without bouncing even $1$ time. This case is the minimum.
Sample 3
Input
1123581321345589
Output
561790660672808
Both the input and the output can be large.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
mine691