ioi2025d1t1

秒赤，好玩。

很神秘的题意，交互但是目标不是得到某个值而是完成一个目标，第一次见。

我们先把交互库返回的东西处理一下，我们想要返回的几样商品的价值和，而不是剩下的钱。我们记返回值为 [a,b,c,...],x，方括号里的是商品集合，

x

是它们的价值和。

首先我们发现询问

\ge P[0]

的值是不合法的，不然

P[0]

就买了；过于小的值也是很危险的，毕竟你不知道

P[n-1]

是什么，万一小于它你就买不到东西，也是不合法的。那么第一步我们能干什么？唯一安全的值应该是

P[0]-1

。

知道了这个后，我们来手玩一下小数据，比如

n=3

。

第一步问

P[0]-1

，会有两种情况：

返回 [1] x。这下我们直接知道 $P[1]=x$ ，接着问一次 $P[1]-1$ 就能知道 $P[2]$ 了。
返回 [1,2] x。这该怎么办！1 号商品已经没有剩余购买次数了，下一步只能买一个 2。这意味着我必须找出一个 $x'\in[P[2],P[1])$ 来询问。容易发现 $x'=\lfloor\frac{x}{2}\rfloor$ 满足条件。

这下

n=3

就解决了，拼盘 39pts 到手。

这个过程中，有几个点很有启发性：

找出一个 $x'\in[P[2],P[1])$ 来询问：如果我们能够对每个 $i\in[1,n-1]$ ，都找到一个 $x\in [P[i],P[i-1])$ 询问一次，这样获得的信息会构成一组 $n-1$ 元线性方程组，而且是满秩的（因为这样一次询问， $i$ 商品一定会被买，且只有 $\ge i$ 的商品可能会被买，因此是对角线全为 1 的上三角），可以直接消元得到每一个 $P[i]$ 。而且如果对于每个 $[P[i],P[i-1])$ 恰好询问一次，一定能满足 $i$ 被买了 $\le i$ 次，不够的在解出 $P[i]$ 后补上即可。
$x'=\lfloor\frac{x}{2}\rfloor$ 满足条件：这提示我们使用上次询问的商品的平均价格来进行下次询问。因为这个平均一定会落在最大值和最小值之间，至少是安全的。
知道 $P[i]$ 的值后， $x'=P[i]-1$ 一定属于 $[P[i+1],P[i])$ ，可以直接用。

有了这些前提后，我们定义一个求解函数

f(S,x)

，其中

S

是一个商品编号集，

x

是

S

中商品的价值和（这个信息是由一次向交互库询问得来的）。这个函数做的事情是，求出

\ge \min(S)

的所有商品的具体价值。

记

\min(S)=m

，那么显然这个

(S,x)

是上一次询问了一个

x'\in[P[m],P[m-1])

得来的。为了满足每个

[P[i],P[i-1])

恰好询问一次，我们需要保证

m

只会作为

\min(S)

出现一次。这个记忆化一下就好。

具体做法是：

每次进入这个函数，所有已知商品价格的 $i$ 一定形成一段后缀（这个是函数本身的进行过程保证的）。我们不断检查 $\max(S)$ 的价格是否已经确定，如果是，就删除 $\max(S)$ 并相应的更新 $x$ 。（这一步其实是在消元）
（如果此时 $|S|>1$ ）基于启发点 (2)，求出剩余物品的平均价格 $avr=\lfloor\frac{x}{|S|}\rfloor$ 并进行一次询问。注意此时 $\min(S)$ 和 $\max(S)$ 之间的所有值我们应该都不知道，相应的所有 $[P[i+1],P[i])$ 也都没有被询问过，所以进行这个询问是合理的。询问完以后递归处理。
重复 1，2 两步直到 $|S|=1$ 。此时容易发现 $\min(S)$ 应该仍然是 $m$ ，这个时候显然 $P[m]=x$ 。由启发点 (3)，此时我们获得了 $x-1\in[P[m+1],P[m])$ ，如果 $m+1$ 没有被处理过，那么询问一次 $x-1$ 并递归处理。

最开始询问一次

P[0]-1

并调用即可。

最后显然可能有物品没买够的，既然我们已经求出所有物品的价格，询问

P[i]

就能恰好买一个

i

，补上即可。

最后补一句，容易发现这个 5000 次交互是假的。每次至少得买一个，总共最多买

1+2+\dots+99=4950

次，根本不怕这个次数上限。

文章操作