Problem Overview

This problem involves calculating the winning probability in a game defined by two random processes: an N-sided die and a fair coin. The objective is to reach a specific threshold K starting from a value generated by the die roll.

Game Mechanics

1. Initialization: Roll an N-sided die. The outcome serves as the initial score, ranging from 1 to N with equal probability.
2. Coin Flipping Loop: If the current score is strictly less than K, flip a fair coin repeatedly.
   • If Heads appear, double the current score.
   • If Tails appear, the score resets to 0 immediately, resulting in a loss.
3. Termination: The game concludse when the score either reaches or exceeds K (a win) or drops to 0 (a loss).

Objective

Given integers N and K, determine the total probability that the player wins. Output should maintain high precision to satisfy absolute or relative error constraints up to 10^-9.

Mathematical Derivation

To find the overall success rate, sum the probabilities of winning for each possible initial die roll.

For a specific face value v obtained from the die:

• If v >= K, the win condition is met instantly. Probability contribution = 1/N.
• If v < K, calculate the minimum number of consecutive heads m required such that v * (2^m) >= K.
  • The probability of achieving this sequence of m heads is (0.5)^m.
  • The contribution for this specific die face is 1/N * (0.5)^m.

Summing these contributions across all faces from 1 to N yields the final answer.

Implementation

The following C++ solution encapsulates the logic into a structured function. It iterates through all dice outcomes, calculates the necessary flips for each, and accumulates the weighted probabilities using standard I/O streams.

#include <iostream>
#include <iomanip>

// Function to compute total winning probability
void solve_dice_coin_game() {
    int num_faces;
    long long target_limit;

    // Read input parameters
    if (!(std::cin >> num_faces >> target_limit)) return;

    double accumulated_probability = 0.0;

    // Iterate over every possible outcome of the die roll
    for (int i = 1; i <= num_faces; ++i) {
        long long current_value = i;
        double current_win_chance = 1.0;

        // Simulate doubling process until reaching or exceeding limit
        while (current_value < target_limit) {
            current_value *= 2;
            current_win_chance /= 2.0;
        }

        // Add weighted probability to the total sum
        accumulated_probability += (current_win_chance / static_cast<double>(num_faces));
    }

    // Output result with high precision formatting
    std::cout << std::fixed << std::setprecision(12) << accumulated_probability << std::endl;
}

int main() {
    // Fast I/O setup
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve_dice_coin_game();

    return 0;
}

Sample Analysis

Consider the case where N=3 and K=10:

• Face 1: Needs 4 doubles to reach 8 -> 16. Wait, 12^4=16 >= 10. Actually, 12^3=8 (fail), 1*2^4=16 (win). So 4 flips. Prob = 1/3 * 1/16 = 1/48.
• Face 2: 22^2=8 (fail), 22^3=16 >= 10. Wait, 22^2=8. Need one more? No. 2->4->8->16. 3 flips. 28=16. Correct. Prob = 1/3 * 1/8 = 1/24.
• Face 3: 3->6->12. 2 flips. Prob = 1/3 * 1/4 = 1/12.

Total = 1/48 + 2/48 + 4/48 = 7/48 ≈ 0.145833333333.