题解作者：regymm
出题人、验题人、文案设计等：见 Hackergame 2022 幕后工作人员。
-
题目分类：math
-
题目分值：200
这个估算圆周率的经典算法你一定听说过：往一个 1 x 1 大小的方格里随机撒 N 个点，统计落在以方格某个顶点为圆心、1 为半径的 1/4 扇形区域中撒落的点数为 M，那么 M / N 就将接近于
当然，这是一个概率性算法，如果想得到更精确的值，就需要撒更多的点。由于撒点是随机的，自然也无法预测某次撒点实验得到的结果到底是多少——但真的是这样吗？
有位好事之徒决定借此和你来一场轮盘赌：撒 40 万个点计算圆周率，而你需要猜测实验的结果精确到小数点后五位。为了防止运气太好碰巧猜中，你们约定五局三胜。
源代码：monte_carlo.zip。运行环境为 debian:11 容器，详见源代码压缩包中的 Dockerfile。
你可以通过 nc 202.38.93.111 10091 来连接，或者点击下面的 "打开/下载题目" 按钮通过网页终端与远程交互。
如果你不知道
nc是什么，或者在使用上面的命令时遇到了困难，可以参考我们编写的 萌新入门手册：如何使用 nc/ncat？
应该不难分析出这是随机数利用的题。蒙特卡罗部分的实现并没有漏洞，但这个随机数：
srand((unsigned)time(0) + clock());
却确实不那么随机。并且更要命的是，因为之后（最多）五次蒙特卡罗都是在连续使用随机数，在随机数种子被设定之后，所有计算结果相当于已经确定了。
而怎么找到随机数种子（直接在服务器上撞明显不是好办法）也不难，因为五局三胜，我们明显可以先故意失败两次，看到前两次的正确结果，然后在本地暴力查找，对每个种子进行两次蒙特卡罗并和正确结果对比，直到确定服务器上的随机数种子。本地和服务器时间相差不会太大，而 clock() 也不过一千多，在 nc 连接 timeout 之前跑出随机数种子乃至后面的正确结果完全不成问题。
遍历程序如下，用 gcc solv.c -O3 -lm 编译，在 nc 连接后立刻运行，输入前两个服务器提示的正确结果之后等着就好了：
这还只是单核，完全没有优化，就足够解题了。
蒙卡确实是个好玩的东西，但随机数使用不当确实会导致一些问题，随机性不够真的会导致模拟结果出偏差（某计算物理 A 课程中会提到这些东西，并留作业画图观察性能不好的随机数种子生成的随机数落在了三维空间里屈指可数的几个平面上）。