solution

Bài toán kim Buffon cổ điển: thả ngẫu nhiên một cây kim dài $L$ xuống mặt phẳng kẻ các vạch song song cách đều nhau khoảng cách $D$ ($L \le D$). Xác suất kim cắt một vạch bất kỳ là $p = \dfrac{2L}{\pi D}$, từ đó có thể ước lượng $\pi$.

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.

Mô phỏng: Cho $L, D$ (số nguyên, $1\le L\le D\le 1000$) và số lần thả kim $N$. Ở lần thả thứ $i$ ($i=1,\dots,N$), lấy hai số ngẫu nhiên kế tiếp $u_{2i-1}, u_{2i}$:

• Khoảng cách từ tâm kim đến vạch gần nhất: $x_i = u_{2i-1} \cdot \dfrac{D}{2}$ (thuộc $[0, D/2)$).
• Góc giữa kim và các vạch: $\theta_i = u_{2i} \cdot \dfrac{\pi}{2}$ (thuộc $[0, \pi/2)$).

Kim CẮT một vạch nếu $x_i \le \dfrac{L}{2}\sin\theta_i$. Gọi $C$ là số lần cắt trong $N$ lần thả.

• Nếu $C = 0$ (không chia được cho 0), in ra undefined.
• Ngược lại, in ước lượng $\hat\pi = \dfrac{2LN}{DC}$, làm tròn 6 chữ số thập phân.

Ví dụ: $L=1,\ D=2,\ N=5,\ \text{seed}=1$ → 5.000000.