F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Twelve Months

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 180    Accepted Submission(s): 47
Special Judge

Problem Description
It is 23:55 on December 31. Squark is playing Twelve Months.

Twelve Months is a poker divination game well-known in some regions of China. It is believed to be able to predict one¡¯s luck in each month in the coming year on New Year¡¯s Eve. 48 cards, a standard 52-card deck excluding 4 Kings, are used in the game. First the 48 cards are shuffled randomly and evenly distributed into 12 stacks facedown. Each stack stands for a month, i.e. the first stack stands for January, the second stack stands for February, etc. Then, starting from the first stack, the player repeats the following process until all the cards are opened in the current stack.

1.Open the topmost unopened card from the current stack;

2.Move to the stack pointed by the number of the card just opened (Ace is the first, Jack is the eleventh and Queen is the twelfth), i.e. the new stack becomes the current stack.

According to the prediction, the player will be lucky in a month if the stack standing for the month is cleared, i.e. all the cards in that stack are opened. Of course, each player can only do the divination once in one year. Repeating the divination will have no effect. Maybe you have realized that the first stack will always be cleared, so the player will always be satisfied because he/she will be at least lucky in the coming month.

Squark has distributed his cards and opened a few of them according to the rule. Suddenly, an urgent phone call comes and interrupts his game. It is from Sevenkplus asking him about some difficult algebraic geometry problems. These problems are so difficult that Squark spends a lot of time but solves none of them. When Squark comes back to his cards, they has been gathered and put into one stack. Squark cannot restore the game to the situation when he left. Furthermore, Squark cannot play the game again as the clock has passed 12 o¡¯clock and it is January 1 now. Fortunately, Squark can still remember the cards he opened and the exact open sequence. So he wants to know the probability of each possible result if he could have continued the game.

As January is always a lucky month, there are 211 possible results regarding the luckiness in the other months. We define a comparison method for these results to sort them, which compares the luckiness in December first, and then in November, and so on. To be unlucky is considered to be smaller than to be lucky.

To simplify the work to test your program, Squark considers the number of months in each year to be n instead of 12. In this way, the number of possible results is 2n - 1 instead of 211.

Input
The first line contains an integer T (T ¡Ü 40) denoting the number of the test cases.

For each test case, the first line contains 2 integers n(2 ¡Ü n ¡Ü 12) and m(0 ¡Ü m ¡Ü 4n), where n is the number of months in each year and m is the number of cards Squark opened. The second line contains m integers, standing for the cards opened by Squark (1 for Ace, 11 for Jack and 12 for Queen) in the order how Squark opened them. Note that the second line is a blank line if m = 0.

Output
For each test case, output 2n - 1 lines, each containing a real number representing the probability of each possible result in the order as described above. Your answer is considered to be correct if and only if it satisfies at least one of the two conditions below.

1.The absolute error is at most 10-12;

2.The relative error is at most 10-9.

Sample Input
2
2 4
2 2 2 2
2 0		

Sample Output
0.0000000000000
1.0000000000000
0.5000000000000
0.5000000000000

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-06-17 03:32:47, Gzip enabled Administration