反恐识别真话者
Counter Strike
题目详情
有 名卧底，其中少于一半是恐怖分子，其余是反恐者。
- 反恐者永远说真话。
- 恐怖分子可能撒谎以误导你。
一次询问为：问 号“ 号是不是反恐者？”。
目标：用尽量少的询问找到至少一个反恐者。
提示：可以做到少于 次询问；构造一条链。
N undercover agents have been found in don's lair. Less than half of them are terrorists and the rest are anti-terrorists. The nature of their job is so secret that there is no proof what so ever to testify who is who. Although each of them knows who was actual terrorist and who was anti because they worked in teams. A query consists of asking person i if person j is Anti. Anti will always speak truth but a terrorist may lie to confuse you. The goal is to find out one anti in fewest queries.
Hint
It can be done in less than N queries. End of a chain is testified by one anti somewhere in the middle.
解析
一种可行思路（ 次量级）：构造一条“链” ，使得每次询问 关于 都得到回答“是反恐”。
关键性质：若链中存在反恐者，则链的最后一个人必为反恐者（因为从某个真话者开始，后续回答都可信）。
再利用“恐怖分子少于一半”的前提，通过逐步扩展/重置链，最终可保证得到包含反恐者的链，从而识别出一个反恐者。
Original Explanation
Solution
Please note that this question cannot be solved with any algorithm if terrorists are more than or equal to anti, because terrorists can plan to always lie.
Another solution taking only N-1 queries: We will try to find a chain of persons (i1,i2,i3....im) such that each ij is queried about i(j+1) and answer is correct. Note that if such chain contains an anti then last person in the chain would be anti. So query person 1 about 2. If answer is yes query person 2 about 3. continue till answer is correct. suppose at some point person i when queried about person j says wrong, in that case remove person i and j from the chain, and continue query process by querying predecessor of i about successor of j. Here note that when we remove person i and j from the chain at-least one of them must be faulty. here for each person except the first one, we are querying once. Hence N-1 comparison in worst case. Think about the best case using this algorithm.