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: Xét bước ngẫu nhiên (random walk) 1 chiều bắt đầu tại vị trí $0$: ở mỗi bước, vị trí tăng $+1$ với xác suất $p/q$ và giảm $-1$ với xác suất $1-p/q$ ($0 < p < q \le 1000$, $p,q$ nguyên).

Mô phỏng $M$ phép thử độc lập, mỗi phép thử gồm $T$ bước. Các số ngẫu nhiên được lấy TUẦN TỰ theo đúng thứ tự toàn cục: phép thử $1$ dùng lần lượt $T$ số ngẫu nhiên đầu tiên (mỗi số cho một bước), rồi đến phép thử $2$ dùng $T$ số tiếp theo, v.v. Ở bước thứ $t$ của một phép thử, lấy số ngẫu nhiên kế tiếp $u$: nếu $u < p/q$ thì bước $+1$, ngược lại bước $-1$.

Với mỗi phép thử, kiểm tra xem vị trí có quay lại đúng $0$ ít nhất một lần SAU khi đã đi ít nhất 1 bước hay không (không tính vị trí xuất phát ban đầu). Sau khi mô phỏng xong $M$ phép thử, tính:

1. Xác suất ước lượng quay lại $0$: (số phép thử có quay lại $0$)$/M$ (quy ước $=0$ nếu $M=0$).
2. Vị trí trung bình cuối cùng (trung bình cộng vị trí sau $T$ bước của $M$ phép thử) (quy ước $=0$ nếu $M=0$).

In 2 giá trị trên, mỗi giá trị làm tròn 6 chữ số thập phân, cách nhau khoảng trắng.

Ví dụ: $M=3,\ T=4,\ p=1,\ q=2,\ \text{seed}=1$ → 0.666667 1.333333.