Deal or No Deal is a TV game show that originated in Holland, but now is broadcasted in many countries over the world. It has some variants in the number of prizes, the number of rounds and the amounts of money that can be won. Here we will study a typical format. Initially 15 candidates recieve a numbered box (number 1 trough 15) with in it each a cheque for an amount of money between 10 and 500,000 Euro. The boxes are closed and the different amounts were assigned randomly to the 15 boxes beforehand, so the candidates don’t know which amount is in which box. The game starts when one candidate is selected to play the game. He takes his box center-stage and then plays upto 4 rounds. In the first round, the candidate calls out 4 of the 14 remaining numbers (not his own) and these boxes are opened and the enclosed amounts are displayed. Now it is sure the candidate’s box contains one of the remaining 11 amounts, but not which. Based on the remaining amounts, the candidate is offered a deal: he can leave the show with a certain amount of money (the deal), or continue playing (no deal). If he decides to continue playing, in the second round he has to appoint 3 more of the remaining boxes (not his own), which are then opened and the enclosed amounts are shown. Then again a deal is offered based on the undisclosed amounts, which the candidate can take or leave. In each of the remaining two rounds (if played), three more boxes are opened and a deal is offered. If the candidate refuses the final deal when only two boxes are left, one of which is his own box, he has to open his box and the enclosed amount is his. The fifteen amounts in the boxes are: 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000 and 500000 Euro. The deal the candidate is offered in each round is a percentage of the average of the remaining amounts. In the first round this percentage is low to tease the candidate to continue playing, but during the following rounds the percentage steadily increases. Although the actual percentages are unknown to the public, statistical analysis of previous game shows reveal that they lie around the same values between shows. Let’s take the following values as an example: 10%, 20%, 40% and 80% for rounds 1 to 4 respectively. To calculate the deals, we break off remainders after division, so if in some round n boxes remain with a total amount of S and the percentage is p, then the offer is the integer part of (S ∗ p)/(100 ∗ n). Let’s illustrate a typical game, where the candidate refuses all deals. It is depicted in the following table: Round Boxes 1 4 2 3 3 3 4 3 Amounts in Selected Boxes 200, 5000, 20000, 50000 10, 50, 2000 1000, 200000, 500000 20, 10000, 100000 Remaining Amounts 10, 20, 50, 100, 500, 1000, 2000, 10000, 100000, 200000, 500000 20, 100, 500, 1000, 10000, 100000, 200000, 500000 20, 100, 500, 10000, 100000 100, 500 Percentage Deal 10 7397 20 20278 40 8849 80 240 So the candidate wins either 100 or 500 Euro, with equal chance, while at some point in the game he could have walked away with about 20,000 Euro. Notice however that at that point he had a fair chance of winning a (much) higher amount of money, but eventually the luck was against him. The Problem
2/3 As you see, the spread of amounts a candidate can win is enormous, and during the game he has to make several hazardous decisions. This makes the game attractive to a lot of people, both to play and to watch. And guess what: someone you know has been selected to play in the show! Because she’s a clever girl, she wants to play using the following strategy: before the show she selects a certain limiting amount of money; whenever, during the show, she is offered that amount or a higher one, she’ll take that deal. If all offers are lower, she will play to the end. Because she is clever, but a bad statician, she asks your advise. Given a certain limiting amount she wants you to calculate two values: the probability that she will win at least this amount of money, and the expected amount she will win when she follows her strategy with this limit. As you know, the expected outcome of an event is the sum, over all possible events, of the products of outcome and probability for that particular event. Input Several cases, each consisting of two lines. The first line contains one integer between 10 and 500000 (inclusive), a limiting amount in Euros for the strategy described. The second line contains 4 integers between 1 and 200 (inclusive), the percentages for rounds 1 to 4 respectively. A line containing a zero terminates the input and should not be processed. Output Two numbers per case, separated by one space, on a line by itself, denoting the probability (between 0.0 and 1.0) and the average amount won (in Euros). A special corrector will tolerate an absolute error of 10−6 and 10−2 for the two values respectively. Epilogue (not needed to solve the problem) The game Deal or No Deal was originally invented by EndemolProductions as part of a bigger game show Miljoenenjacht (Hunt for the Millions). In this original format the game was played with 26 suitcases and prizes ranging from 0.01 to 5,000,000 Euro. Now the show airs in more than 30 countries and has it’s own page in Wikipedia. Scientifically the show is interesting to social scientists and economists, because it gives an op- portunity to study human behaviour under rapidly changing gain/loss situations. Deal or No Deal?Decision Making Under Risk in a Large-payoff Game Show (Post et.al. 2006) is one such study, that concludes that people are more willing to cut a reasonable deal after they have sustained a big loss. In the example given in the problem statement, most people would accept the deal in round 3 after loosing two major opportunities, even though the expected earning when continuing is more than double the amount of the deal. At the same time, most people would reject the much higher deal in round 2, because the perspectives of winning even higher amounts are still reasonable. Our clever friend in the problem statement would have won at least her limit of 20,000 Euros in about two-thirds of the cases. The situation in the game show is not much different from real life (Stock Exchange, Job Market, Real Estate, etc.), although maybe a bit more extreme. Endemol likes to put people under extreme circumstances; they also created Big Brother and Fear Factor. Sample Input 20000 10 20 40 80 10 10 25 50 100 500000 5 15 55 105 0
3/3 Sample Output 0.675991 25507.05 1.000000 5925.43 0.066667 59258.67