问题 21308 --假金币

21308: 假金币

时间限制: 3 Sec  内存限制: 128 MB
提交: 7  解决: 6
[提交][状态][讨论版][命题人:]

题目描述

“Gold Bar”银行收到可靠消息:在前次的N 个金币中有一枚重量不同的假金币(其他金币的重量都相同)。经济危机之后他们只有一台天平可用。用这台天平,可以称量出左边托盘中的物体是轻于、重于或等于右边托盘中的物体。
为了分辨出假金币,银行职员将所有的金币编为1到N号。然后用天平称量不同的金币组合,每次仔细记载称量金币的编号和结果。 
现在要求你编写一个程序,帮助银行职员根据称量记录来找出假金币的编号。

输入

第一行输入两个空格隔开的整数N和K,N是金币的总数(2<=N<=1000 ) , K是称量的次数(1<=K<=100)。随后的2K行记录称量的情况和结果,连续两行记录一次称量:第一行首先是Pi (1<=Pi<=N/2),表示两边托盘中放置的金币数目,随后是左边托盘中Pi个金币编号和右边托盘中Pi个金币编号,所有的数之间都由空格隔开;第二行用'<','>','='和记录称量结果: 
'<'表示左边托盘中的金币比右边的轻;
'>'表示左边托盘中的金币比右边的重; 
'='表示左右两边托盘中的金币一样重。

输出

输出假金币的编号。如果根据称量纪录无法确定假金币,输出0。

样例输入

5  3
2 1 2 3 4
<
1 1 4
=
1 2 5
=

样例输出

3

提示


思路:



这个题可以用蛮力搜索来解决。

从题目描述,数据的规模不大,而时间限制足够大,选择暴力搜索可以使程序设计简单,而且因为是完全搜索,所以不会出现漏掉解的情况。



思路很简单:把所有的金币都试一遍。

Step 1:依次假设I号金币是假的;

Step 2:对称量的记录进行监测;如果假设与所有的记录都不矛盾,则有可能是假的。

Step 3:如果有可能是假的金币只有1个,输出它的编号;否则,输出0。

来源

 

[提交][状态]