Description

$N$ people sit in a circle to play a game. At the beginning, all players are numbered clockwise from $1$ to $N$. In the first round, player $1$ is the dealer. In each round, the dealer randomly (i.e., with equal probability) selects one card from the deck. Suppose the number on the card is $X$. The dealer first shows $X$ to all players, then, counting clockwise starting from the dealer’s position, the $X$-th person is eliminated (i.e., leaves the game). The card is then returned to the deck and the deck is reshuffled. The next person clockwise after the eliminated player becomes the dealer for the next round. After $N-1$ rounds, only one person remains, who is the winner. You are given that there are $M$ cards in total and the number on each card. You need to determine the winning probability of each player.

Here is a simple example:

For example, there are $4$ players and four cards with the numbers 3,4,5,6.

In the first round, the dealer is player $1$. Suppose they draw a card with the number $5$. Counting clockwise 1,2,3,4,1, player $1$ is eliminated.

In the second round, the dealer is the next player after player $1$, i.e., player $2$. Suppose player $2$ now draws a card with the number $6$. Counting 2,3,4,2,3,4, player $4$ is eliminated.

In the third round, player $2$ is again the dealer. If player $2$ draws $6$ again, then player $3$ is eliminated, and the winner is player $2$.

Input Format

The first line contains two integers $N, M$, the number of players and the total number of cards.

The next line contains $M$ integers, giving the number on each card.

Output Format

Output one line containing $N$ real numbers in percentage form, rounded to two decimal places. These are the winning probabilities of players $1$ through $N$, separated by single spaces, with no trailing space at the end.

5 5
2 3 5 7 11

22.72% 17.12% 15.36% 25.44% 19.36%

4 4
3 4 5 6

25.00% 25.00% 25.00% 25.00%

Hint

• For $30\%$ of the testdata, $1 \le N \le 10$.
• For $50\%$ of the testdata, $1 \le N \le 30$.
• For $100\%$ of the testdata, $1 \le N \le 50$, $1 \le M \le 50$, and $1 \le$ each card’s number $\le 50$.

Translated by ChatGPT 5