Sadistic coach P92727


Statement
 

pdf   zip

thehtml

Professor Oak’s latest perversion is to compute the maximum number h of consecutive hours that his students can train before exploding. He already locked one student alone for n ‍hours in a computer room. Sadly, the student could not resist the effort. When Prof. ‍Oak opened the room’s door, the remainings of the student where scattered all around.

Prof. Oak assumes that all his students have the same resistance. He also assumes that it is equally likely that h is 0, 1, …, or n − 1. He wants to determine h, but minimizing the expected number of experiments. Additionally, he does not want to sacrifice more than two additional students (they are too valuable). What is the optimal expected cost?

For instance, for n=4 the optimal cost is 2: First, we lock a student (Ivan, for example) for 2 hours. If he does not explode, which will happen with probability 2/4, we lock Ivan again for 3 hours. If Ivan does explode during his first experiment, we lock another student (Xavi, for instance) for 1 hour. This way, the (expected) total cost is obviously 2.

Note that initially locking Ivan for 3 hours would be a worse strategy: If he exploded, which would happen with probability 3/4, we should lock Xavi for 1 hour, and afterwards perhaps lock Xavi again for 2 hours, for a total expected cost of 9/4.

Input

Input consists of several cases, each one with a natural number n between 1 and 107.

Output

For every n, print the optimal expected cost to compute h, with four digits after the decimal point. The input cases have no precision issues.

Public test cases
  • Input

    1
    2
    3
    4
    5
    10000000
    949
    

    Output

    0.0000
    1.0000
    1.6667
    2.0000
    2.4000
    2982.4236
    30.0000
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++