2013
12-30

Cover Up

In the Price Is Right’s game Cover Up, players test their luck to win a new car. To win, the player must produce the actual retail price of the car from a board of possible numbers like:

The player selects one number from each column to form a bid. Using the above board as an example, the first number in the price of the car is either 1 or 3; the second is one of 9, 4, 2; the third is one of 0, 6, 8, 4; and so on. Numbers may never move to a different column.

After the player selects their bid, Drew Carey lights up the numbers in the bid which are correct. If the player has no numbers correct, the game ends and they lose; if they have at least one number correct, the game continues.

When the game continues, the player is given another opportunity to select numbers from those columns that were incorrect. They will cover up the wrong bid numbers with different selections from the same columns. Again, Drew Carey will light up any new correct digits. If the player has no new numbers correct, the game ends and they lose; if they have at least one new number correct, the game continues.

For example:

The player selects an initial bid of $14677. The 1, 4 and first 7 are correct (c stands for correct, x for incorrect, and v designates a column that requires a subsequent selection in the example above). The player covers up the incorrect 6 and 7 with an 8 and a 3 for a second bid of$14873. The 3 is correct, but the 8 is wrong. At this point it’s a 50/50 chance. The player will select the 4 or the 0 and either win the car or lose the game.

The show’s sponsors would like to know how frequently their cars are given away. You are to use the assumption that players choose numbers uniformly from those remaining.

The sponsor will explore many variations, with prices up to 7 digits long. Therefore, the input file will begin with a line containing the integer N <= 5000, the number of test cases to be explored. The test cases follow.

Each test case begins with the integer d, 0 < d <= 7, the number of digits in the price of the car. d lines will follow, with non-empty strings of *distinct* digits in the range from 0 through 9. Each of these lines represents a *column* of the digits in the game. The first line represents the leftmost column; the last the rightmost column. A 0 is possible as the first digit in the price of the car.

The sponsor will explore many variations, with prices up to 7 digits long. Therefore, the input file will begin with a line containing the integer N <= 5000, the number of test cases to be explored. The test cases follow.

Each test case begins with the integer d, 0 < d <= 7, the number of digits in the price of the car. d lines will follow, with non-empty strings of *distinct* digits in the range from 0 through 9. Each of these lines represents a *column* of the digits in the game. The first line represents the leftmost column; the last the rightmost column. A 0 is possible as the first digit in the price of the car.

2
2
9
19
5
13
942
0684
34720
947368

1.000
0.321

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮