README.md

超自动的开箱模拟器

• 题目分类：math

• 题目分值：200

想体验开箱的快乐吗？

这是一个开箱模拟器。当你输入「BF 开箱码」之后，程序会模拟 128 轮游戏，每轮你有 64 次开箱机会。

如果你 128 轮中每轮都能够在 64 次机会之内找到目标所在的箱子，那么你将会得到 flag。

点击下载 源代码

打开/下载题目

---

分析源代码可知，题目是做这样的一件事情：

在 128 轮模拟中，每一轮你的 Brainfuck 语言程序会与一个开箱模拟器进行交互。

你的程序输出 1、2、3 分别表示向左移动、向右移动、开箱。

你有 64 次开箱机会，开箱后你的程序的输入将得到开箱的结果。

每一轮中你都需要在 64 次机会内成功找到包含 target 数字的箱子，而 target 数字在这 128 轮中各不相同。

箱子是随机排列打乱的，每一轮的顺序完全相同，但是你的程序无法在轮与轮之间携带信息。

这个问题被称为百囚徒问题（100 prisoners problem）。

看似不可能的挑战，其实只要每个人像链表一样把打开箱子的内容作为下一个打开的箱子的编号，就可以以非常高的概率成功。

这是因为，把箱子内数字的置换拆解成一堆不相交的循环，只要最大的循环的阶小于等于 64，所有人就都可以成功，而这样的概率大约是 0.3 左右。

具体的数学证明可自行查阅“百囚徒问题”相关资料。

接下来我们要做的事情就是用 Brainfuck 语言实现这个开箱逻辑，这里有个坑在于箱子内的数字是 1128，而箱子本身的下标是 0127。

如何编写 Brainfuck 代码可以参考相关的资料，这里我手工编写的代码如下：

+> >+>++>+++<<< <[> -[>.< -] , - [>>.<< -] >>>.<<< <]

它的功能是循环做以下事情：输入一个数（上一个箱子里的数），减一得到 n，然后把位置移动到最左（输出很多次 1），再向右移动 n 次（循环，每次数字减一的同时输出 2，直到数字变为 0），最后开箱（输出 3）

多提交几次即有非常大的概率可以拿到 flag。

花絮

我本来想把百囚徒困境出成一个简单的交互题，但这是做不到的，因为我们需要选手提交一个“策略”，这个“策略”需要在不同的环境下被执行很多次，并且不同次之间不能传递任何信息。如果直接让选手来开箱，那么无法做到不同次之间不传递信息。所以我让选手提交图灵完备的 Brainfuck 语言代码来表示“策略”，模拟器也比较好实现。

使用向左向右移动和开箱操作，而不是直接让程序输出开箱的位置，是故意的设计。这是想让选手真正理解这个问题之后再进行尝试，而不是随便试几个简单的符号组合（甚至在不理解 Brainfuck 各种符号的含义的情况下）就把题目解出了。