娱乐 奇怪的算法挑战【第②期？】寻找宝物

[Muriya Tensei]

一座奇怪的地牢中有一件宝物，宝物存在于宝箱之中，而在这个地牢中有着无数外观相同的宝箱，你的手中却只有一把一次性的钥匙可以打开其中一个宝箱。并且一旦进入地牢，就会触发机关，如果宝物没有被拿到，那么地牢将在一定时间后重置，可能没有充足的时间来尝试检查宝箱。

万幸的是，你的巫师朋友告诉你，他能为你制作一种卷轴若干，卷轴可以花费一些时间，来探测宝物，一个卷轴可以同时探测许多的宝箱，并不会耗费更多的时间，当探测到有宝物存在时，卷轴就会碎裂，也许你就能知道宝物所在的位置了。（ps：如果没检测到的话，卷轴还能继续使用，但是每张卷轴每次检测都需要花费一定的时间）

你思维十分敏锐，选择用哪些卷轴来探测哪些宝箱并不会花费时间，并且发现宝箱之后可以瞬间将其打开拿到宝物，这样。朋友为你准备了充足的卷轴，但是告诉你，在一个地牢使用过的卷轴就没办法在其他地方使用了，因此只要你每动用了一个卷轴就给他一颗魔晶石。

已知：地牢经过 t 时间就会重置，而你的卷轴检测需要花费 c 的时间，在你进入地牢之后发现，其中有 n 个宝箱。

那么你最少需要多少魔晶石才能找到宝物呢？

 

例如：2个宝箱，1分钟后地牢重置，卷轴检测花费1分钟。

你需要 1 颗魔晶石即可。

解释：你只需要用一个卷轴就能够发现一个宝箱中是否有宝物，那么你瞬间就能知道宝物的位置并拿到，因此你只需要1颗魔晶石。

 

又如：4个宝箱，10分钟后地牢重置，卷轴检测花费7分钟。

你需要 2 颗魔晶石。

 

[Muriya Tensei]

12 分钟前, mamamama 说道:

我读出来的意思是要在 t 时间内完成解谜，t/c 限制了一张卷轴一直失败的最大使用次数

是这个意思没有错

8 小时前, 子之半 说道:

天平？次数最少？

重置啥意思？

具体重置什么，宝箱内容物的位置会不被因重置

就是理解成一个限时任务就行，只能在规定时间内完成

[Muriya Tensei]

22 分钟前, mamamama 说道:

优化目标是最少卷轴数，应该是 t/c=1 的时候采用二进制分组，需要卷轴个数为 log₂n 上取整。而当 t/c>=n-1 的时候可以用一个卷轴一路试过去。

再后面的我没看懂了

 

盲猜答案应该是 t/c+1 进制分组，要 n 开 t/c+1 次方根个

有东西的.jpg，那么可以不盲猜来提供一下具体方法或者思路吗

十二月 16, 2021，由Muriya Tensei修改

[Muriya Tensei]

45 分钟前, mamamama 说道:

方法就是

把 n 个箱子按 0 到 n-1 编号，把它们写成 t/c+1 进制的形式，需要的卷轴数就等于最大位数

第 0 轮（为了方便从 0 开始了）的时候第 k 个卷轴就去验所有第 k 位为 0 的箱子

第 1 轮的时候每个卷轴去验对应位为 1 的箱子

这样验 t/c 轮之后，就可以确定每一位是 0 到 t/c 中的哪个数了，也就确定了答案的编号

 

大概……应该……（小声），信息和次数全用满了

可以说是相当完善了，用信息熵可以确认m≥⌈log(t/c+1) n⌉，并且用进制表示的方法很简单的也能描述出m=⌈log(t/c+1) n⌉的实现方法