CasinoGame
SRM 643 · 2014-08-25 · by Errichto
SRM 643 · 2014-08-25 · by Errichto · Math
Problem Statement
Problem Statement
You are playing a game in a casino.
The game is played with a sequence of positive real numbers.
You are given a
During the game, some elements of the sequence will become erased. Once an element has been erased, it remains erased for the rest of the game. The game ends when all elements have been erased.
Your initial score is zero.
The game is played in turns. Each turn has three phases:
- An element of the sequence that hasn't been erased yet is chosen uniformly at random.
- That element is added to your score and then erased.
- A random effect is applied to each element that hasn't been erased yet.
For each element, the random effect that will be applied is randomly chosen as follows:
- With probability 33% the element is erased (without being added to your score).
- With probability 33% the element is divided by two. (If its current value is x, its new value will be x/2.)
- With probability 33% the element is replaced by its square root. (If its current value is x, its new value will be sqrt(x).)
- With probability 1% the element is restored to its initial value. (Regardless of its current value, its new value will be the value it had before the first turn of the game.)
Return the expected value of your score at the end of the game.
Notes
- The returned value must have an absolute or relative error less than 1e-9.
Constraints
- S will contain between 1 and 1,000 elements, inclusive.
- Each element of S will be between 1 and 1,000,000, inclusive.
Examples
0)
{100000, 100000}
Returns: 120.80000000000001
We start the game with the sequence {100, 100}. Regardless of which element is chosen in the first step, our score will increase by 100 and that element will be erased. Let's consider what will happen to the other element: With probability 33% the other element is also erased, the game ends, and our score is 100. With probability 33% the element becomes 50. In the second turn we add it to our score and we end the game with the score 150. With probability 33% the element becomes 10. In the second turn we add it to our score and we end the game with the score 110. With probability 1% the element is restored to its initial value, which means that it will remain 100. In this case our final score will be 200. Thus, our expected final score is 0.33*100 + 0.33*150 + 0.33*110 + 0.01*200.
1)
{68391}
Returns: 68.391
2)
{9000, 25000, 100000}
Returns: 59.47600366439891
The initial sequence is {9, 25, 100}. One possible gameplay looks as follows: Element 1 is selected, added to your score, and erased. Element 0 is halved and element 2 is replaced by its square root. The new sequence is {4.5, erased, 10}. Element 0 is selected, added to your score, and erased. Element 1 is already erased, so nothing happens there. Element 2 is restored to its original value. The new sequence is {erased, erased, 100}. Element 2 is selected, added to your score, and erased. The game ends. In this game your final score was 25 + 4.5 + 100 = 129.5.
3)
{932452, 32431, 234511, 1, 999, 12341, 432134, 987654, 1000000}
Returns: 569.7984079363877
4)
{655482,657692,166545,510808,406135,487463,572526,89578,844121,881092,843697,733297,998007,518962,879347,652488,193968,569275,486335,194222,498550,98979,729632,518857,959392,22656,728919,158737,793281,75238,760687,449635,732925,558907,592118,770734,47242,165516,491986,891358,678283,336555,257207,308841,487191,137426,961324,681154,338375,80210,
875371,468599,809986,237554,987452,770250,891008,348922,928983,685161,424155,690542,766471,788754,881123,359461,560360,928360,156651,684020,452270,466608,21447,341151,775444,140312,110251,369319,821461,448621,81203,329383,548895,891185,566933,168898,662307,458813,517815,223841,775648,573645,546058,174670,363271,428053,165805,555306,357286,322452,
240198,441230,420734,892443,414055,827853,33627,524301,828846,855084,604596,910045,816141,154363,802102,15625,323256,96960,106112,472746,320797,881756,47263,866850,688100,410529,295775,853901,597509,284735,808027,837703,357639,229633,362697,771689,58358,396319,927664,518879,883077,533133,429796,700091,687491,863572,715711,642422,592206,821819,
116040,912998,336126,794100,412399,25098,836303,339849,510673,434685,256258,319572,904062,613893,180880,267631,18133,239233,663945,945793,389786,179574,111477,819577,879660,430642,315700,227922,73936,907902,681415,820773,453451,649215,615745,865846,674309,452921,837369,816656,519280,94499,137101,424214,340066,317976,691840,988997,188883,386109}
Returns: 817.8156226417173
5)
{1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}
Returns: 1650.8120310299312
Here S has 1,000 elements, all equal to 1,000,000.
Submissions are judged against all 22 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CasinoGame with a public method double expectedValue(vector<int> S) · 22 test cases · 2 s / 256 MB per case