問題一覧 > 通常問題

No.1459 I Just Want to Drop My Smartphone

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 84
作問者 : Noboru2020 / テスター : butsurizuki shiomusubi496
お気に入りにしたユーザー ProblemId : 5774 / 自分の提出
問題文最終更新日: 2021-03-31 20:19:05
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
新入生プログラミングコンテスト 2021（夜の部） (順位表) の他の問題:

Problem Statement

In the year $2100$, Noboru has finally achieved his long-cherished goal of developing a "very hard-to-break smartphone".
However, as things stand, people will surely think it is just like any other dubious smartphone out there.
With that in mind, Noboru decided to use the $N$-story Shinpuro Building to find the integer $A$ satisfying the following [Conditions], and to sell the smartphone with the slogan "It won't break even if dropped from floor $A$ of the Shinpuro Building".

[Conditions]

  • $0 \le A \le N$
  • For any $x$ satisfying $1 \le x \le A$, the smartphone does not break when dropped from floor $x$
  • For any $y$ satisfying $A < y \le N$, the smartphone always breaks when dropped from floor $y$

    • It is guaranteed that such an $A$ exists, that $A$ is the same for all smartphones, and that $A$ stays constant as long as the smartphone is not broken.
    Now, Noboru has asked you to find $A$.
    So you have decided to actually drop smartphones from the Shinpuro Building.
    However, smartphones are very expensive, so you can use only $2$ smartphones in the experiment.
    A smartphone can be dropped from the Shinpuro Building any number of times as long as it does not break, but of course a broken smartphone can no longer be used.
    When you follow a strategy that makes the number of drops in the worst case as small as possible, find that number.

    Input

    $N$
    • $1 \le N \le 10^9$
    • $N$ is a positive integer

    Output

    Output the minimum possible number of drops in the worst case on one line, followed by a newline.

    Sample

    Sample 1
    Input
    2
    Output
    2

    For example, the following strategy can be used.

    1. From floor $1$, drop smartphone number $1$. If it breaks, then $A=0$; otherwise, proceed to the next step.
    2. From floor $2$, drop smartphone number $2$. If it breaks, then $A=1$; otherwise, $A=2$.

    With this strategy, $A$ can be determined with certainty in $2$ drops. There is no way to determine $A$ with certainty in $1$ drop or fewer, so output $2$.

    Sample 2
    Input
    10
    Output
    4

    Sample 3
    Input
    1
    Output
    1

    That is hardly a building anymore, is it?

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