Put the two halves together: a seeded generator makes the random numbers, and a categorical sampler turns them into outcomes. Then compare what happened with what was expected.
What to build
A program that draws n samples with a linear congruential generator and compares the counts with their expected values.
Requirements
- For each of n samples: x ← (a × x + c) mod m, r = x / m, then choose the first outcome whose running total of probabilities (weights divided by their sum) is greater than r.
- Print the samples on one line.
- Then for each outcome, in order:
LABEL: COUNT (expected E), with E = n × p to 2 decimal places.
Input
Line 1: a, c, m, seed and n. Line 2: the labels. Line 3: the weights.
Output
1 + number of outcomes lines.
Constraints
1 ≤ m ≤ 10⁹; 1 ≤ n ≤ 1000; 1 to 50 outcomes.
Example
Input:
5 3 16 7 5
heads tails
1 1
Output:
heads heads tails tails tails
heads: 2 (expected 2.50)
tails: 3 (expected 2.50)
Why it works
The generator supplies numbers spread over [0, 1), and the sampler maps each to an outcome in proportion to its probability; with few samples the counts wander around n × p, as the output shows.
Examples
5 3 16 7 5 heads tails 1 1
heads heads tails tails tails heads: 2 (expected 2.50) tails: 3 (expected 2.50)
1 1 10 0 4 a b c 1 1 2
a a b b a: 2 (expected 1.00) b: 2 (expected 1.00) c: 0 (expected 2.00)
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Generate each random number with x = (a × x + c) % m and r = x / m.
Hint 2
Sample the outcome for r as in "Sample from weighted outcomes".
Hint 3
The expected count of an outcome is n × its probability.
Solution
Show one correct solution (try it yourself first)
a, c, m, x, n = map(int, input().split())
labels = input().split()
weights = list(map(float, input().split()))
total = sum(weights)
chosen = []
for _ in range(n):
x = (a * x + c) % m
r = x / m
running = 0.0
pick = labels[-1]
for label, w in zip(labels, weights):
running += w / total
if r < running:
pick = label
break
chosen.append(pick)
print(*chosen)
for label, w in zip(labels, weights):
print(f"{label}: {chosen.count(label)} (expected {n * w / total:.2f})")