ThePriceIsRightGuessing
SRM 833 · 2022-07-08 · by misof
Problem Statement
In the game show The Price Is Right the players are shown an item. The price of the item (in dollars) is an unknown positive integer. The players are trying to guess that price.
More precisely, the guessing proceeds sequentially. One after another, each player announces a positive integer - their guess. All guesses must be distinct - you may not guess the same value another player already announced.
Once all players announce their guesses, the winner is determined using two rules:
- Each player who guesses more than the actual price is eliminated.
- Out of the players who remained, the one closest to the actual price wins the item.
You are the last one to play.
The players before you have all made their guesses.
You are given these guesses in the
You assume that the actual price will be between 1 and MAX dollars, inclusive, and that each of these prices is equally likely.
What guess should you make? Return the guess that will give you the biggest chance to win the object. If there are multiple optimal solutions, return the smallest one among them.
Constraints
- previousGuesses will have between 0 and 500 elements, inclusive.
- MAX will be between 5 and 10^12, inclusive.
- Each element of previousGuesses will be between 1 and MAX, inclusive.
- Elements of previousGuesses will be distinct.
- The number of elements in previousGuesses will not exceed MAX-1.
{1, 3, 5, 7, 9}
10
Returns: 2
The price you are guessing is between 1 and 10, inclusive. Your five opponents have already guessed all five odd numbers. Regardless of what guess you now make, you will win the iten only if your guess is exactly right. For example, let's examine what happens if you make the guess "2 dollars": If the actual price is $1, the player who guessed "1" gets it. (Everyone else guessed too high and so they are eliminated.) If the actual price is $2, you get the item. (Everyone other than you and the player who guessed "1" is eliminated. Out of the two of you, your guess is closer - in fact, exactly right.) If the actual price is $3 or $4, the player who guessed "3" gets the item. If the actual price is $5 or $6, the player who guessed "5" gets the item. ... and so on. Remember that if there are multiple optimal options, you must choose the smallest one of them. In this case, even though all the even numbers give you the same chance of winning (10 percent), you must return the smallest one among them.
{}
47
Returns: 1
You have no opponents. It should be pretty obvious what guess is the optimal guess in this situation. (Note that if you guessed that the price is $15 and it turned out to be only $12, you would be eliminated and nobody would get the item.)
{100000000000, 300000000000, 500000000000, 700000000000, 900000000000}
1000000000000
Returns: 100000000001
Almost example 0, but scaled. Now there are many more guesses to choose from. (Watch out for integer overflow!)
{1, 9, 5, 2, 4, 10, 7, 3, 8}
10
Returns: 6
The last constraint guarantees that you will still be able to make a valid guess. In this example your hand is forced: the only price that hasn't been guessed yet is $6 and so that's what you have to choose. (Technically, you are also allowed to make a guess greater than MAX, but doing so is clearly pointless as it does not give you any chance to win the item.)
{1, 9, 5, 2, 4, 10, 7, 3, 8}
11
Returns: 6
{1, 10}
20
Returns: 11
The guess "11" gives you a 50% chance to win the item: if the price is anywhere between 11 and 20, inclusive, the item is yours. Each other valid guess gives you a smaller chance. For example, the guess "5" only gives you a 25% chance to win the item. If you were to announce "5" as your guess, you would win the item if the price is in the set {5, 6, 7, 8, 9}.
Submissions are judged against all 93 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ThePriceIsRightGuessing with a public method long long guess(vector<long long> previousGuesses, long long MAX) · 93 test cases · 2 s / 256 MB per case