这是本文档旧的修订版!
给定 $n$ 个磁体,编号 $1\sim n$。磁体有三种类型 $S,N,-$,其中 $-$ 代表无磁性。允许 $n+\lfloor \log n\rfloor$ 次询问。
每次询问选择若干磁体,分成两组,然后用装置测量两组磁体之间的受力。
其中,设第 $i$ 组有 $s_i$ 个 $S$ 型磁体,$n_i$ 个 $N$ 型磁体,则受力为 $s_1s_2+n_1n_2-s_1n_2-s_2n_1$,若受力超过 $n$ 则测量装置损坏。
要求在不损坏装置的前提下在允许询问次数内找到所有无磁性磁体。
数据保证至少有两个有磁性的磁体和一个无磁性的磁体。
每次询问 $1\sim i-1$ 和 $i$ 号磁体两组之间的受力,当受力不为 $0$ 时 $i$ 号磁体一定有磁性,$1\sim i-1$ 中一定恰有一个有磁性磁体。
考虑二分找到 $1\sim i-1$ 中的有磁性磁体,然后用第 $i$ 号磁体检验 $i+1\sim n$ 磁体的磁性。查询次数 $n-1+\lceil \log n\rceil$。