假金币问题-PKUacm1029-ACM

假金币

“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
#include <stdio.h>
int ids[126][1024];
int op[126];
int n,k; bool isTrue(int id){
int i;
bool isTrue = false;
for(i=0;i < k;i++){
int j;
bool found;
found = false;
for(j = 1;j<=(ids[i][0]<<1);j++){
if(ids[i][j] == id){
found = true;
break;
}
}
if(found && op[i] == '=' || !found && op[i]!='='){
//如果找到了,并且实验结果为相等。
//或者,未找到,且实验结果不等(即有问题的金币在当前组中)
//则id编号的金币一定是为真的金币
isTrue = true;
break;
}
}
return isTrue;
} int main(){ scanf("%d%d",&n,&k); //输入金币数和测试数据组数
if(!(2<=n && n <=1000) || !(1 <= k && k <= 100)){
return 1;
}
int i,j;
for(i = 0;i < k;i++){
scanf("%d",&ids[i][0]); //输出本次实验每个盘上放置的金币个数
for(j = 1;j <= (ids[i][0]<<1);j++){
scanf("%d",&ids[i][j]); //依次输入金币编号
}
scanf("%*c%c",&op[i]);
} //从第1个金币开始,迭代校验第i个金币是否为真
for(i = 1; i <= n ;i++){
if(!isTrue(i)){
//false_id = i;
break;
}
}
printf("%d",i);
return 0;
}
上一篇:MongoDB系列三(Spring集成方案).


下一篇:android从应用到驱动之—camera(2)---cameraHAL的实现