問題一覧 > 通常問題

No.1286 Stone Skipping

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

問題文

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

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

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

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

入力

DD
  • 1≤D≤10181\le D\le 10^{18}
  • DD は整数

出力

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

サンプル

サンプル1
入力
10
出力
6

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

サンプル2
入力
5
出力
5

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

サンプル3
入力
1123581321345589
出力
561790660672808

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

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