問題一覧 > 通常問題

No.1286 Stone Skipping

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 211
作問者 : 👑 箱星 / テスター : mine691
お気に入りにしたユーザー ProblemId : 4948 / 自分の提出
問題文最終更新日: 2022-04-25 23:51:20
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
yukicoder contest 274 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。