Given at Least One Six

In a dice game you roll n six-sided dice. A friend peeks and tells you: "at least one die shows a six". What is now the probability that the total is at least target?

Write check_by_simulation(n, target, trials, seed) that answers the question twice and returns a tuple (kept, hits, estimate, exact):

• Simulation. Create rng = random.Random(seed). For each of trials trials, roll the n dice in order with rng.randint(1, 6) each (exactly n calls per trial, nothing else from rng). kept is the number of trials with at least one six, hits the number of those with a total of at least target, and estimate = hits / kept (or None if kept is 0).
• Exact. exact is the true conditional probability, as a tuple (numerator, denominator) in lowest terms, found from all 6 ** n equally likely rolls.

Examples

Input:  n = 2, target = 10, trials = 0, seed = 1
Output: (0, 0, None, (5, 11))
Explanation: 11 of the 36 rolls contain a six. Of these, (4,6), (6,4), (5,6), (6,5) and
(6,6) have a total of at least 10, so the exact answer is 5/11. No trials were run.

Input:  n = 2, target = 10, trials = 2000, seed = 3
Output: (591, 284, 0.4805414551607445, (5, 11))
Explanation: 591 of the 2000 simulated trials had a six, and 284 of those reached 10:
an estimate of 0.48 against the exact 5/11 = 0.4545.

Constraints

• 1 <= n <= 6, n <= target <= 6 * n + 1
• 0 <= trials <= 20000
• floats are compared with a tolerance of 1e-6

Goals

• Estimate a conditional probability by simulation, keeping only the trials where the condition holds
• Compute the same conditional probability exactly by counting outcomes
• Use a seeded random generator in a precisely specified way so results are reproducible