# Solution of;
# Project Euler Problem 527: Randomized Binary Search
# https://projecteuler.net/problem=527
# 
# A secret integer t is selected at random within the range 1 ≤ t ≤ n. The 
# goal is to guess the value of t by making repeated guesses, via integer g. 
# After a guess is made, there are three possible outcomes, in which it will 
# be revealed that either g < t, g = t, or g > t. Then the process can repeat 
# as necessary. Normally, the number of guesses required on average can be 
# minimized with a binary search: Given a lower bound L and upper bound H 
# (initialized to L = 1 and H = n), let g = ⌊(L+H)/2⌋ where ⌊⋅⌋ is the integer 
# floor function. If g = t, the process ends. Otherwise, if g < t, set L = 
# g+1, but if g > t instead, set H = g−1. After setting the new bounds, the 
# search process repeats, and ultimately ends once t is found. Even if t can 
# be deduced without searching, assume that a search will be required anyway 
# to confirm the value. Your friend Bob believes that the standard binary 
# search is not that much better than his randomized variant: Instead of 
# setting g = ⌊(L+H)/2⌋, simply let g be a random integer between L and H, 
# inclusive. The rest of the algorithm is the same as the standard binary 
# search. This new search routine will be referred to as a random binary 
# search. Given that 1 ≤ t ≤ n for random t, let B(n) be the expected number 
# of guesses needed to find t using the standard binary search, and let R(n) 
# be the expected number of guesses needed to find t using the random binary 
# search. For example, B(6) = 2. 33333333 and R(6) = 2. 71666667 when rounded 
# to 8 decimal places. Find R(1010) − B(1010) rounded to 8 decimal places.
# 
# by lcsm29 http://github.com/lcsm29/project-euler
import timed


def dummy(n):
    pass


if __name__ == '__main__':
    n = 1000
    i = 10000
    prob_id = 527
    timed.caller(dummy, n, i, prob_id)

# Solution of;
# Project Euler Problem 527: Randomized Binary Search
# https://projecteuler.net/problem=527
# 
# A secret integer t is selected at random within the range 1 ≤ t ≤ n. The 
# goal is to guess the value of t by making repeated guesses, via integer g. 
# After a guess is made, there are three possible outcomes, in which it will 
# be revealed that either g < t, g = t, or g > t. Then the process can repeat 
# as necessary. Normally, the number of guesses required on average can be 
# minimized with a binary search: Given a lower bound L and upper bound H 
# (initialized to L = 1 and H = n), let g = ⌊(L+H)/2⌋ where ⌊⋅⌋ is the integer 
# floor function. If g = t, the process ends. Otherwise, if g < t, set L = 
# g+1, but if g > t instead, set H = g−1. After setting the new bounds, the 
# search process repeats, and ultimately ends once t is found. Even if t can 
# be deduced without searching, assume that a search will be required anyway 
# to confirm the value. Your friend Bob believes that the standard binary 
# search is not that much better than his randomized variant: Instead of 
# setting g = ⌊(L+H)/2⌋, simply let g be a random integer between L and H, 
# inclusive. The rest of the algorithm is the same as the standard binary 
# search. This new search routine will be referred to as a random binary 
# search. Given that 1 ≤ t ≤ n for random t, let B(n) be the expected number 
# of guesses needed to find t using the standard binary search, and let R(n) 
# be the expected number of guesses needed to find t using the random binary 
# search. For example, B(6) = 2. 33333333 and R(6) = 2. 71666667 when rounded 
# to 8 decimal places. Find R(1010) − B(1010) rounded to 8 decimal places.
# 
# by lcsm29 http://github.com/lcsm29/project-euler
import timed


def dummy(n):
    pass


if __name__ == '__main__':
    n = 1000
    i = 10000
    prob_id = 527
    timed.caller(dummy, n, i, prob_id)

# Solution of; # Project Euler Problem 527: Randomized Binary Search # https://projecteuler.net/problem=527 # # A secret integer t is selected at random within the range 1 ≤ t ≤ n. The # goal is to guess the value of t by making repeated guesses, via integer g. # After a guess is made, there are three possible outcomes, in which it will # be revealed that either g < t, g = t, or g > t. Then the process can repeat # as necessary. Normally, the number of guesses required on average can be # minimized with a binary search: Given a lower bound L and upper bound H # (initialized to L = 1 and H = n), let g = ⌊(L+H)/2⌋ where ⌊⋅⌋ is the integer # floor function. If g = t, the process ends. Otherwise, if g < t, set L = # g+1, but if g > t instead, set H = g−1. After setting the new bounds, the # search process repeats, and ultimately ends once t is found. Even if t can # be deduced without searching, assume that a search will be required anyway # to confirm the value. Your friend Bob believes that the standard binary # search is not that much better than his randomized variant: Instead of # setting g = ⌊(L+H)/2⌋, simply let g be a random integer between L and H, # inclusive. The rest of the algorithm is the same as the standard binary # search. This new search routine will be referred to as a random binary # search. Given that 1 ≤ t ≤ n for random t, let B(n) be the expected number # of guesses needed to find t using the standard binary search, and let R(n) # be the expected number of guesses needed to find t using the random binary # search. For example, B(6) = 2. 33333333 and R(6) = 2. 71666667 when rounded # to 8 decimal places. Find R(1010) − B(1010) rounded to 8 decimal places. # # by lcsm29 http://github.com/lcsm29/project-euler