## Intuition The problem asks us to calculate the expected maximum number of dots that can be obtained after tossing a dice with `m` faces, `n` times. The key insight is to understand how the probability distribution of the maximum value changes as we increase the number of tosses. For each face `k` (1 to `m`), the probability that the maximum value after `n` tosses is exactly `k` can be calculated by considering: - The probability that all `n` tosses result in values less than or equal to `k`. - The probability that at least one of these tosses results in exactly `k`. ## Approach 1. **Probability Calculation**: - For a given face `k`, calculate the probability that all `n` tosses result in values less than or equal to `k`. This is given by \((\frac{k}{m})^n\). - Similarly, calculate the probability that all `n` tosses result in values less than or equal to `k-1`. This is \((\frac{k-1}{m})^n\). 2. **Expected Value Calculation**: - The probability that the maximum value is exactly `k` is the difference between the two probabilities calculated above: \((\frac{k}{m})^n - (\frac{k-1}{m})^n\). - Multiply this probability by `k` to get the contribution of face `k` to the expected maximum. - Sum these contributions for all `k` from 1 to `m` to get the expected maximum. 3. **Implementation**: - Use a loop to iterate over each face from 1 to `m`. - Accumulate the expected value contributions as described. ## Complexity - **Time**: \(O(m)\) because we iterate over each face from 1 to `m`. - **Space**: \(O(1)\) since we only use a few variables to store intermediate results. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin >> m >> n; double expected_maximum = 0.0; for (int k = 1; k <= m; ++k) { double prob_k = pow((double)k / m, n); double prob_k_minus_1 = pow((double)(k - 1) / m, n); double prob_exactly_k = prob_k - prob_k_minus_1; expected_maximum += k * prob_exactly_k; } cout << fixed << setprecision(12) << expected_maximum << '\n'; return 0; } ``` This solution efficiently computes the expected maximum by iterating over each possible maximum face value and calculating its contribution to the expected value using probability theory. The use of `pow` function allows us to compute the necessary probabilities for each face efficiently.

Little Pony and Expected Maximum

Problem Details