有 Delay 的猜数问题
今天看到一道很趣味的交互题啊！
可爱 @WatanukiTaiga 教会了我这道题的扩展版本，非常厉害😍！
Hard version
交互库藏起来了一个 \([1, 10^9]\) 之间的整数，你每次可以猜一个数。
交互库会告诉你大了还是小了，还是猜对了，你需要在 \(30\) 次以内猜出这个数。
我相信大家都会！这是不是太简单了一点？
还能再给力一些吗？
Medium version
交互库藏起来了一个 \([1, 10^9]\) 之间的整数，你每次可以猜一个数。
交互库会告诉你大了还是小了，还是猜对了，你需要在 \(60\) 次以内猜出这个数。
但是因为交互库换成了笨蛋，所以交互库存在延迟，交互库会在你的第 \(t\) 次询问告诉你你的第 \(t - 1\) 次询问的结果。（第一次没有返回）
想必大家用了 1s 就能秒掉吧！是不是还是太简单了一点？
还能再给力一些吗？
如果我们要求在 \(44\) 次之内猜出呢？
Source: Indonesia NOI 2023, Day2 ProblemC
放下你那可笑的 \(2\log\) 做法！
我们来想想，现在应该怎么办？
可以发现，Hard version 的做法能够保证在 \(\log_{2}(10^9)\) 次之内询问出来，其本质原因在于，每次问题规模都会至少缩小到原来的 \(\dfrac{1}{2}\)。
注意到保证询问次数规模的关键其实是：不论是得到了什么样的回复，都能够将问题缩小同等规模。
由于交互库存在延迟回复，我们没有办法保证每个操作都能将问题每次都缩小相同的规模。
所以我们有一个启发，不妨考虑第一次我们不问中间的，我们稍微问偏一点，看看会有什么事情发生。
假设问题规模初始为 \(V\)，我们第一次询问了 \(x\)，第二次询问了 \(y\) 并且 \(x > y\)，并不妨假设我们询问 \(x\) 的时候“认为”答案应该在 \([x, V]\) 当中。
第二次询问时返回的结果会有这两种情况：
- 交互库回答了“小了”，这说明，我们的“认为”是错误的，那么问题规模会缩小到 \([1, x]\)。
- 交互库回答了“大了”，这说明，我们的“认为”是正确的，但是我们浪费了 \(y\) 这次询问，问题规模变成了 \([x, V]\)。
我们发现，第一种情况并没有浪费第二次操作，我们将问题规模减小了 \(V - x\)，第二种情况浪费了第二次操作，将问题规模减小了 \(x\)。
我们希望每个操作不管怎么样，都能够降低问题的规模。
不妨令 \(x + y = V\)，（不要问我为什么，MOer 的思维我搞不懂233）于是我们发现 \(V - x < x\)，那么其实第一种情况可以看作，第一次操作让问题规模减小到了 \(x\)，第二种则可以看作第一次操作让问题规模减小到了 \(x\)，第二次操作将问题规模再次减小到了 \(y\)，于是这个浪费的操作就有了作用，并且你发现不管怎么样一个操作的贡献其实固定了。
回到刚才的想法，我们想让每个操作都可以将问题缩小同等规模，于是我们可以按照 Fibonacci 数列来对当前的问题进行划分，这又是怎么想到的呢？
不妨设 \(N(t)\) 表示在 \(d = 1\) 的限制下，\(t\) 次询问能问出的数的上界。
按照我们刚才的想法，一种情况是知道了 \(t - 1\) 次操作并没有浪费，另一种情况是操作被浪费了，它没用了，但是我们以上面的方式对这个操作进行了补偿，那么对应下来 \(N(t) = N(t - 1) + N(t - 2)\)。
于是我们发现，按照这个进行划分，然后做一个形如二分的东西，就好了！
换句话说，正常的二分规模是类似 \(1, 2, 4, 8, 16\)。
我们这里变成了 \(1, 2, 3, 5, 8, 13\)。
还能再给力一些吗？
Easy version
交互库藏起来了一个 \([1, V]\) 之间的整数，你每次可以猜一个数。
交互库会告诉你大了还是小了，还是猜对了，你需要在 \(L\) 次以内猜出这个数。
但是因为交互库换成了笨蛋⑨，所以交互库存在延迟，交互库会在你的第 \(t\) 次询问告诉你你的第 \(t - d\) 次询问的结果。（\(1 \sim d\) 次没有返回）
其实上面的做法的核心思想就是，我们不希望被延迟 \(d\) 次到来的信息打乱，我们希望这个信息到了之后仍然能够缩小范围。
类比，我们可以推出 \(N_{d}(t) = N_{d}(t - 1) + N_{d}(t - d - 1)\)。
于是我们按照这个数列进行划分就能做这个加强版了！