假币 ## 来源 Northeastern Europe 1998 (ZOJ2034, POJ1029) ## 题目描述 一堆共N枚硬币中，有一枚是假币。假币的重量跟真币不一样，真币的重量是一样的。有一台很简单的天平，这台天平可以测出左盘中的重量比右盘中的重量轻、重还是一样。 为了找出假币，银行把N枚硬币标上1～N的整数，这样每个整数唯一地确定了一枚硬币的序号。然后把相同数目的硬币放在天平的左右盘进行称重，每次称重左右盘中硬币的序号以及称重的结果都详细地记录下来。你的任务是编写程序，根据称重的结果找出假币的序号。 ## 输入描述 输入文件包含多个测试数据。第1行为整数T，代表测试数据数目。然后是一个空行，之后是T个测试数据。各测试数据之间有一个空行。每个测试数据的第1行为整数N和K，用空格隔开，N代表硬币的数目，2≤N≤100，K代表称重的次数，1≤K≤100。接下来的2K行描述了这K次称重，连续的两行描述了每次称重。这两行的格式为：第1行首先是整数Pi，1≤Pi≤N / 2，表示此次称重左右盘硬币的数目，然后是放在左盘中的Pi硬币的序号，以及放在右盘中Pi个硬币的序号，所有的数值用空格隔开；第2行是一个符号，为'<'，'>'或'='，含义是：'<'，左盘中的重量轻于右盘中的重量；'>'，左盘中的重量重于右盘中的重量；'='，两盘中的重量相等。 ## 输出描述 对每个测试数据，输出假币的序号，如果根据给定的称重无法判断出假币，则输出0。两个测试数据的输出之间有空行。 ## 样例输入 ```txt 1 5 3 2 1 2 3 4 < 1 1 4 = 1 2 5 = ``` ## 样例输出 ```txt 3 ``` ## 提示 可枚举第1～N枚硬币为假币的情形，如果只有一枚符合三次称重，则找到假币，如果有多枚硬币符合这3次称重，则无法判断。但N的值可以取到200，所以这不是一种好方法。 更好的方法是： (1) 如果天平平衡，则左右秤盘中的硬币被标记为真币，且不再改变； (2) 天平不平衡时，轻盘中各币被标记“轻”一次，重盘中各币被标记“重”一次； (3) 然后扫描所有硬币，凡是被标记“轻”或“重”的次数与天平不平衡次数相等的钱币被重点怀疑。只有一个，则其必定为假币，一个以上，则无法判断； (4) 如果K次称量中天平没有不平衡过，则没有被标记真硬币的钱币被怀疑，只有一个，就是假币，一个以上，也是无法判断。