Four Quarters

Time limit1sMemory limit128 MB

Summary

For each round count from 1 to 20, compute the probability that A wins, B wins, or the game ties after that many rounds of this four-coin game.

Level: Easy3 of 10
Topics: Probability, Dynamic programming, Simulation
Solved: No attempts yet

Problem

Four Quarters is a game of chance played with four 25-cent coins (quarters). Two players, A and B, each flip two coins every round. Based on the results of their own two coins, each player gains or loses points according to the tables below.

A two-coin result is distinguished only by its number of heads; Heads/Tails and Tails/Heads are treated as the same. So each player’s result is one of HH (2 heads), HT (1 head), or TT (0 heads).

Player A’s payoff (rows: A’s result, columns: B’s result)

A / B	B: HH	B: HT	B: TT
A: HH	1	1	2
A: HT	0	0	1
A: TT	-1	0	0

Player B’s payoff (rows: A’s result, columns: B’s result)

A / B	B: HH	B: HT	B: TT
A: HH	0	-1	-1
A: HT	1	0	0
A: TT	2	0	-1

As you can see, the odds are stacked in Player A’s favor. At the start of the game both players have 0 points, and points accumulate as the game progresses. When the game ends, the player with more points wins.

Write a program that determines the probability that Player A wins, Player B wins, or the game ties after a given number of rounds. Assume the coins are fair, i.e. heads and tails are equally likely.

Input

There is no input for this problem.

Output

Output a table listing the probability that Player A wins, Player B wins, or the game ties after each round, for rounds 1 through 20. Express each probability as a percentage with 4 digits after the decimal point.

Print the header line Round A wins B wins Tie first, then one line per round from 1 to 20, each containing the round number followed by the three probabilities. Match the exact spacing and formatting shown in the example output.

Examples1

Example 1

Input

Expected output

Round   A wins    B wins    Tie
    1   43.7500%  18.7500%  37.5000%
    2   56.6406%  22.2656%  21.0938%
    3   62.3535%  22.7051%  14.9414%
    4   65.9134%  22.0657%  12.0209%
    5   68.6609%  21.0665%  10.2726%
    6   70.9815%  19.9854%  9.0332%
    7   73.0088%  18.9226%  8.0686%
    8   74.8079%  17.9104%  7.2816%
    9   76.4212%  16.9569%  6.6219%
   10   77.8796%  16.0617%  6.0587%
   11   79.2070%  15.2222%  5.5709%
   12   80.4219%  14.4346%  5.1434%
   13   81.5393%  13.6954%  4.7653%
   14   82.5709%  13.0010%  4.4280%
   15   83.5266%  12.3482%  4.1251%
   16   84.4146%  11.7339%  3.8515%
   17   85.2417%  11.1553%  3.6030%
   18   86.0137%  10.6098%  3.3764%
   19   86.7359%  10.0952%  3.1690%
   20   87.4124%  9.6092%  2.9784%