WellTimedSearch
TCO13 Round 2C · 2013-02-19 · by misof
Problem Statement
Monicka has an array of N cells, numbered 0 through N-1. She chooses one cell of the array uniformly at random and places a token into that cell.
Misko will then play a game with Monicka, trying to guess the location of the token. The gameplay is similar to binary searching for the token – in each turn, Misko picks a cell of the array and receives one of three possible answers: "left" if the token is in a cell with a smaller number, "right" if it is in a cell with a larger number, or "correct" if the chosen cell contains the token. The game ends when Misko gets the answer "correct".
Misko is not allowed to ask useless questions. For example, if he already chose the cell 47 and received the answer "right", he is not allowed to choose any of the cells 3, 12, and 47: it is already known that these cells do not contain the token.
Monicka does not like games that are too short or too long. She is happy with a game that takes at least A, but at most B turns. Misko wants to make Monicka happy, therefore he aims to finish the game in such a number of turns.
You are given the
Notes
- Return values with absolute or relative error at most 1e-9 will be accepted as correct.
Constraints
- N will be between 1 and 1,000,000, inclusive.
- A will be between 1 and N, inclusive.
- B will be between A and N, inclusive.
3 2 2 Returns: 0.6666666666666666
Monicka will be happy if Misko's second guess is correct. The best strategy for Misko is to choose the index 1 first. If he gets the answer "correct", he won the game too early. But if he gets the answer "left" or "right", he will win the game in the second turn. Thus the probability that Monicka will be happy when Misko uses this strategy is 2/3.
3 3 3 Returns: 0.3333333333333333
This time Misko wants to postpone his correct guess until the third turn.
123456 1 20 Returns: 1.0
Misko can use binary search to guarantee that he will be able to guess Monicka's number in well under 20 guesses.
5 3 4 Returns: 0.6
1 1 1 Returns: 1.0
Submissions are judged against all 137 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WellTimedSearch with a public method double getProbability(int N, int A, int B) · 137 test cases · 2 s / 256 MB per case