You have reached the final round of a game show, and it is time to determine the amount of your prize.
The number of digits, n, in the amount has been determined based on your earlier performance during the game.
You will be presented with a board containing n blank spaces and given n randomly-generated digits.
You will be allowed to place each digit, one at a time, in any unoccupied space you want.
You must decide where to place each digit before you see the next, and once you place a digit you
cannot move it.
After all n digits have been placed, the resulting n-digit number will be the value of your prize.
For example, assume you have earned a three-digit prize.
If the first digit generated were a 2, you might choose to place that in the rightmost space,
hoping that the next two digits will be larger.
If the second digit were a 8, you might choose to place that in the leftmost space,
because you would only regret that decision in the relatively unlikely event that the final digit is a 9.
If the third digit were a 6, you would place that in the last remaining space (the middle), and your
final prize would be 862.
You will be given the state of the number you are forming digit-by-digit as a String digits,
possibly already in progress.
This String will contain one character for each space on the board: '0' through '9', inclusive, indicate digits that have already been placed, and a '_' indicates a blank space on the board.
Assuming you play optimally in order to maximize your expected winnings, return the expected value of the prize you will win.
At each step, each of the digits 0 through 9 will be presented to you with equal probability.
Note that the digits already placed may not be the result of optimal play, but you should assume that
you will play to maximize your expected winnings from this point forward.
|