問題一覧 > 通常問題

No.1286 Stone Skipping

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 198
作問者 : 👑 箱箱 / テスター : mine691mine691
51 ProblemId : 4948 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 23:51:20

問題文

小星さんは水面に向かって石を投げて遊んでいます。石が距離 $x$ だけ飛んで水面に着地するたびに、次のいずれかが起こります。

  • 水面で跳ね返り、距離 $\lfloor\frac{x}{2}\rfloor$ だけ飛んで、再び水面に着地する。
  • 水面で跳ね返らず、その場で沈む。

石の最初の飛距離として好きな正の整数を選ぶことができます。

小星さんは石の総飛距離を $D$ にしたいです。最初の飛距離をいくつにすれば、総飛距離が $D$ になり得るでしょうか。答えが複数ある場合は、最小のものを求めてください。

入力

$D$
  • $1\le D\le 10^{18}$
  • $D$ は整数

出力

石の総飛距離が $D$ となるような最初の飛距離の最小値を出力してください。

サンプル

サンプル1
入力
10
出力
6

最初の飛距離が $6$ のとき、跳ね返るとさらに $\lfloor\frac{6}{2}\rfloor=3$ だけ飛びます。さらに跳ね返ると $\lfloor\frac32\rfloor=1$ だけ飛びます。その後沈むと、総飛距離が $10$ になります。最初の飛距離が $6$ より小さいとき、総飛距離は $10$ にならないので、最小値は $6$ です。

サンプル2
入力
5
出力
5

最初の飛距離を $5$ にして、$1$ 回も跳ね返らずに沈みます。この場合が最小です。

サンプル3
入力
1123581321345589
出力
561790660672808

入力・出力ともに大きくなる場合があります。

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