/* poj 1029 False coin
题目大意:
同1013,查找假的硬币。不过不同的是,不要求求出假币是重还是轻,只需要找出即可。
解题思路:
同1013.
令所有出现在左侧的硬币为1,右侧的硬币为-1,称重结果: 左侧重为1,轻为-1。
则有如下
a、假币较重,其每次的结果与称重结果完全相同 -- 左侧时都为1,右侧时都为-1
b、假币较轻,其每次的结果与称重结果完全相同 -- 左侧时其为1,结果-1;右侧反过来
则最后,只有真正的假币会与所有的测试结果完全相同或者相反 -- 重相同,轻相反。
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
namespace {
using namespace std;
const int N_MAX = 1000;//硬币允许最多总个数
const int K_MAX = 100;//硬币比较允许最多次数
int C[N_MAX+1][K_MAX]; // 记录每枚硬币每次的假设结果
int R[K_MAX]; // 记录真实称重结果
}
int main()
{
int N, K;
//freopen("1.txt","r",stdin);
scanf("%d%d", &N, &K);
int t;
for (int i=0; i<K; i++)
{
int Pi;
scanf("%d", &Pi);
for (int j=0; j<Pi; j++)
{
scanf("%d", &t);
C[t][i] = 1; // 左侧假设为1
}
for (int j=0; j<Pi; j++)
{
scanf("%d", &t);
C[t][i] = -1; // 右侧假设为-1
}
char rs[8];
scanf("%s", rs);
// 本次称重结果
if (rs[0]=='<') R[i]=-1;
if (rs[0]=='=') R[i]= 0;
if (rs[0]=='>') R[i]= 1;
}
bool bFound = true;
int k=0;
for (int i=1 ; i<=N; i++)
{
int c1=0, c2=0;
for (int j=0; j<K; j++)
{
if (C[i][j] == R[j]) // 同为1或-1或0的情况
++c1;
if (C[i][j] == -R[j]) // 同为0或者一个1、一个-1的情况
++c2;
if (C[i][j]!=R[j] && C[i][j]!=-R[j]) // 一个为0一个不为0的情况
break;
}
if (c1==K || c2==K) // 存在完全相同或者完全相反的情况,注意0同属于两种i情况
{
if(k==0)
{
k = i; // 首次找到这种情况,记录之
}
else
{
bFound = false; // 多于一次找到,说明不可判断,停止查找
break;
}
}
}
if (bFound)
printf("%d\n", k);
else
printf("0\n");
return 0;
}
分享到:
相关推荐
西北工业大学POJ试题C++答案代码+课程设计
NULL 博文链接:https://taojianrong.iteye.com/blog/1756785
poj训练 c语言poj训练 西工大 poj 100题。
无解题报告 只有代码 因为此题是水题,代码包含了筛选法求素数的算法。
动态规划 poj Common Subsequence c++ cpp文件
c++ npu poj答案100道全 请勿用于盈利
C + + language learning poj100 question bank and code
北大POJ1321-Chess Problem POJ1321-Chess Problem
解决poj1006问题
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...
北大POJ1003-Hangover 解题报告+AC代码
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
C语言写的,通过了.我第一个POJ通过的文件,纪念一下.POJ上对于格式要求还真是紧啊!
北大POJ1163-The Triangle
北大POJ1163-The Triangle 解题报告+AC代码
递归实现 各种BOOL算 注意C++的判断机制
北大 POJ的水题解答C++版,请合理使用
poj上面的300道AC题,c++源码,自己写的不会有任何问题。
每道题的类型 后面还归纳了poj中的简单题
用贪心算法解决POJ 1065的木棍处理问题