Pseudo-dichotomic search P60373


Statement
 

pdf   zip

thehtml

Consider a hidden vector V with n integer numbers in strictly increasing order. Given an integer ‍x that belongs to V, you will play a game to guess the position j where V[j] = x. You have to use a “black box” B, with parameters x and a position i inside V. If there is a j ∈ {i − 1, i, i + 1 } such that V[j] = x, you win the game. Otherwise, B will tell you whether x < V[i−1] or x > V[i+1].

Given n, what is the minimum number of calls to B to win the game?

Input

Input consists of several cases, each one with an n between 1 and 1018.

Output

For every n, print the worst-case number of calls to B to win the game, assuming a strategy that minimizes that worst-case cost.

Public test cases
  • Input

    1
    2
    4
    9
    10
    1000000000000000
    

    Output

    1
    1
    2
    2
    3
    49
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++