solution

Bộ sinh số giả ngẫu nhiên (để kết quả tái lập được, không dùng random thật): Cho số nguyên seed $\ge 0$. Đặt $s_0=\text{seed}$. Với $i=1,2,3,\dots$: $s_i = (1103515245 \cdot s_{i-1} + 12345) \bmod 2^{31}.$ Số ngẫu nhiên thứ $i$ là $u_i = s_i / 2^{31} \in [0,1)$. Dãy $u_1,u_2,u_3,\dots$ được lấy theo ĐÚNG thứ tự này, dùng tuần tự trong suốt quá trình mô phỏng.

Bài toán: Có $n$ loại phiếu quà tặng ($2\le n\le 500$, riêng $n=1$ vẫn hợp lệ). Mỗi lượt rút phiếu, ta nhận được ngẫu nhiên đều một trong $n$ loại. Bài toán sưu tập phiếu (coupon collector) hỏi: cần rút bao nhiêu lượt để có đủ cả $n$ loại?

Mô phỏng $M$ lần thí nghiệm độc lập (thứ tự số ngẫu nhiên dùng tuần tự toàn cục qua các lần thí nghiệm, lần thí nghiệm trước dùng xong mới sang lần sau). Ở thí nghiệm thứ $j$, tại lượt rút thứ $t$ (tính từ 1, tăng dần không giới hạn theo từng lượt), lấy số ngẫu nhiên kế tiếp $u$ và xác định loại phiếu nhận được là $\text{type} = \lfloor u\cdot n\rfloor + 1$ (thuộc $1..n$). Tiếp tục rút cho đến khi đã nhận đủ $n$ loại KHÁC NHAU, gọi $D_j$ là số lượt đã rút.

Để đảm bảo chương trình luôn dừng, giới hạn an toàn $\text{MAXDRAW} = 20000$: nếu rút đến lượt thứ $20000$ mà vẫn CHƯA đủ $n$ loại, dừng lại và quy ước $D_j = 20000$.

Sau $M$ thí nghiệm, in ra:

1. Số lượt rút trung bình $\bar D = \left(\sum_j D_j\right)/M$ (làm tròn 6 chữ số thập phân; quy ước $=0$ nếu $M=0$).
2. Số lượt rút lớn nhất $\max_j D_j$ trong $M$ thí nghiệm (số nguyên; quy ước $=0$ nếu $M=0$).

Ví dụ: $n=3,\ M=2,\ \text{seed}=1$ → 4.500000 5.