Problem Description

N participants sit in a circle playing an elimination game. Initially, each player is assigned a clockwise number from 1 to N. In the first round, player 1 serves as the dealer. Each round, the dealer randomly draws a card with equal probability from a deck of M cards. If the drawn card shows number X, the dealer reveals it, then counts X participants clockwise (including themsleves) to determine who gets eliminated. The card is returned and the deck is reshuffled. The participant immediately clockwise to the eliminated person becomes the next dealer. After N-1 elimination rounds, only one survivor remains as the winner. Given the deck composition, calculate each player's winnning probability.

Example: With 4 players and cards [3, 4, 5, 6]:

• Round 1: Dealer is player 1. Drawing 5 eliminates player 1 (count: 1→2→3→4→1).
• Round 2: Dealer is player 2. Drawing 6 eliminates player 4 (count: 2→3→4→2→3→4).
• Round 3: Dealer is player 2 again. Drawing 6 eliminates player 3, making player 2 the winner.

Input Format

The first line contains two integers N and M, representing the number of players and cards respectively. The second line contains M integers representing the numbers written on each card.

Output Format

Output N percentages rounded to two decimal places, representing the winning probabilities for players 1 through N, separated by single spaces.

Sample Input/Output

Sample 1

Input:
5 5
2 3 5 7 11

Output:
22.72% 17.12% 15.36% 25.44% 19.36%

Sample 2

Input:
4 4
3 4 5 6

Output:
25.00% 25.00% 25.00% 25.00%

Constraints

• For 30% of data: 1 ≤ N ≤ 10
• For 50% of data: 1 ≤ N ≤ 30
• For 100% of data: 1 ≤ N ≤ 50, 1 ≤ M ≤ 50, 1 ≤ each card value ≤ 50

Solution Approaches

Method 1: State Compression DP (30 points)

We can model the game using bitmask DP. Let dp[dealer][state] represent the probability that a specific player is the dealer when the elimination state is state (bitmask of eliminated players). For each state, we iterate through all possible dealers, cards, compute the eliminatde player, then transition to the next state where that player is marked as eliminated and the next clockwise survivor becomes the new dealer.

#include <bits/stdc++.h>
#define MAXN 55
using namespace std;

int playerCount, cardCount;
int cardValues[MAXN];
double winProb[MAXN];
unordered_map<int, double> currentProb[MAXN], nextProb[MAXN];
set<int> currentStates, nextStates;

int locateTarget(int start, int steps, int eliminationMask) {
    int current = start;
    for (int i = 1; i < steps; i++) {
        current++;
        if (current > playerCount) current -= playerCount;
        while (eliminationMask & (1 << (current - 1))) {
            current++;
            if (current > playerCount) current -= playerCount;
        }
    }
    return current;
}

int main() {
    cin >> playerCount >> cardCount;
    for (int i = 1; i <= cardCount; i++) cin >> cardValues[i];
    
    currentProb[1][0] = 1.0;
    currentStates.insert(0);
    
    for (int round = 1; round < playerCount; round++) {
        currentStates.swap(nextStates);
        nextStates.clear();
        
        for (int i = 1; i <= playerCount; i++) {
            nextProb[i] = currentProb[i];
            currentProb[i].clear();
        }
        
        for (int state : currentStates) {
            for (int dealer = 1; dealer <= playerCount; dealer++) {
                if ((state & (1 << (dealer - 1))) || nextProb[dealer][state] == 0) continue;
                
                for (int card = 1; card <= cardCount; card++) {
                    int steps = cardValues[card] % (playerCount - round + 1);
                    if (steps == 0) steps = playerCount - round + 1;
                    
                    int eliminated = locateTarget(dealer, steps, state);
                    int nextDealer = locateTarget(eliminated, 2, state | (1 << (eliminated - 1)));
                    
                    int newState = state | (1 << (eliminated - 1));
                    currentProb[nextDealer][newState] += nextProb[dealer][state] / cardCount;
                    nextStates.insert(newState);
                }
            }
        }
    }
    
    int finalMask = (1 << playerCount) - 1;
    for (int i = 1; i <= playerCount; i++) {
        printf("%.2lf%% ", currentProb[i][finalMask ^ (1 << (i - 1))] * 100.0);
    }
    return 0;
}

Method 2: Optimized DP with Renumbering (100 points)

The bottleneck of Method 1 is the exponential state space. Instead of tracking exact eliminated players, we can work backwards from the final state. Define prob[remaining][position] as the probability that player position survives when there are remaining players left and player 1 is always the dealer. The key insight is that when a player is eliminated, we can renumber the remaining players to maintain consistent indexing.

Base case: prob[1][1] = 1 (only one player remains).

Transition: For remaining players, consider each possible survivor position and each card. The card value determines an offset t from the dealer. If position is before the eliminated player, its new index becomes position + remaining - t. If after, it becomes position - t. Accumulate probabilities from the remaining-1 state.

#include <bits/stdc++.h>
#define MAXN 55
using namespace std;

int totalPlayers, totalCards;
int cardValues[MAXN];
double dp[MAXN][MAXN]; // dp[remaining][position]

int main() {
    cin >> totalPlayers >> totalCards;
    for (int i = 1; i <= totalCards; i++) cin >> cardValues[i];
    
    dp[1][1] = 1.0;
    
    for (int remaining = 2; remaining <= totalPlayers; remaining++) {
        for (int pos = 1; pos <= remaining; pos++) {
            for (int card = 1; card <= totalCards; card++) {
                int offset = cardValues[card] % remaining;
                if (offset == 0) offset = remaining;
                
                if (pos < offset) {
                    dp[remaining][pos] += dp[remaining - 1][pos + remaining - offset] / totalCards;
                } else if (pos > offset) {
                    dp[remaining][pos] += dp[remaining - 1][pos - offset] / totalCards;
                }
            }
        }
    }
    
    for (int i = 1; i <= totalPlayers; i++) {
        printf("%.2lf%% ", dp[totalPlayers][i] * 100.0);
    }
    return 0;
}