問題一覧 > 通常問題

No.1459 スマホを落としたいだけなのに

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 81
作問者 : Noboru2020Noboru2020 / テスター : butsurizukibutsurizuki shiomusubi496shiomusubi496
9 ProblemId : 5774 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-31 20:19:05

問題文

$2100$ 年、 Noboru 君はついに悲願であった「とっても割れにくいスマホ」の開発に成功した。
しかし、このままではそこらへんの怪しいスマホと同じだと思われてしまうに違いない。
そう考えた Noboru 君は、 $N$ 階建ての新プロビルを使い、 次の【条件】を満たす整数 $A$ を見付けて、「新プロビルの $A$ 階から落としても割れません」という売り文句で売り出すことにした。

【条件】

  • $0 \le A \le N$
  • $1 \le x \le A$ を満たす任意の $x$ について、 $x$ 階からスマホを落としてもスマホは割れない
  • $A < y \le N$ を満たす任意の $y$ について、 $y$ 階からスマホを落とすと必ずスマホは割れる

    • ただし、このような $A$ は存在することが保証されているとし、全てのスマホで $A$ は等しく、割れない限りは $A$ は一定であるとする。
    さて、 Noboru 君はあなたに $A$ を求めてほしいと依頼してきた。
    そこで、あなたは実際に新プロビルからスマホを落としてみることにした。
    だが、スマホはとっても高級品なので、実験では $2$ つのスマホしか使えない。
    スマホは割れない限り新プロビルから何回でも落とせるが、当然割れたスマホはもう使えない。
    最悪の場合の落とす回数ができるだけ小さくなるように戦略を取るとき、その回数を求めよ。

    入力

    $N$
    • $1 \le N \le 10^9$
    • $N$ は正の整数である

    出力

    最悪の場合の落とす回数の最小値を一行に出力し、最後に改行してください。

    サンプル

    サンプル1
    入力
    2
    出力
    2

    例えば、次のような戦略が取れます。

    1. $1$ 階から $1$ つめのスマホを落とす。もし割れたなら $A=0$ 、そうでなければ次に進む。
    2. $2$ 階から $2$ つめのスマホを落とす。もし割れたなら $A=1$ 、そうでなければ $A=2$ となる。

    この戦略を取ると、 $2$ 回で $A$ を確実に特定できます。 $1$ 回以下で $A$ を確実に特定する方法はないため、 $2$ を出力します。

    サンプル2
    入力
    10
    出力
    4

    サンプル3
    入力
    1
    出力
    1

    もはやビルではないですね。

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