A seeded sampler with expected counts

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

Example 1 · Input
5 3 16 7 5
heads tails
1 1
Expected output
heads heads tails tails tails
heads: 2 (expected 2.50)
tails: 3 (expected 2.50)
Example 2 · Input
1 1 10 0 4
a b c
1 1 2
Expected output
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})")

Lesson: Sampling and randomness →