A player collects trading cards with n distinct types. Each draw yields card type i with probability pi. Duplicate cards convert to coins, where k coins can be exchanged for one missing card. The process continues until all card types are collected. Compute the expected number of draws required.

Input Format

First line: n (card types) and k (coins needed per exchange)
Second line: Probabilities p1 to pn

Output Format

Expected number of draws (floating-point with precision 10-4)

Constraints

• 1 ≤ n ≤ 16
• 1 ≤ k ≤ 5
• pi ≥ 0.0001
• ∑pi = 1

Solution Approach

This is a probability expectation problem solvable via dynamic programming with state compression. Key aspects:

1. Represent card collection state as a bitmask (n-bit integer)
2. Track current coins as a sepraate state variable
3. Use memoization to store intermediate results

State Transition

For state (bitmask, coins):

• If all cards collected: return 0
• If coins ≥ k × missing_cards: exchange and return
• Else: For each possible next draw, compute weighted expectation

// Pseudocode for DP solution
function solve(bitmask, coins):
    if all_cards_collected(bitmask):
        return 0
    if coins >= k * missing_cards(bitmask):
        return 0
    if memo[bitmask][coins] exists:
        return memo[bitmask][coins]
    
    expectation = 1  // current draw
    for card in 1..n:
        prob = p[card]
        new_bitmask = bitmask | (1 << card)
        new_coins = coins + (bitmask & (1 << card) ? 1 : 0)
        expectation += prob * solve(new_bitmask, new_coins)
    
    memo[bitmask][coins] = expectation
    return expectation