/* 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;
}
分享到:
相关推荐
《C++经典代码大全》是一份集合了作者自编的C++编程实例,主要涵盖了POJ(Problem Set of Peking University)在线判题系统上的众多经典编程题目。这份资源对于初学者来说尤其宝贵,因为它提供了丰富的实践案例,...
【标题】"西北工业大学C++ POJ答案"指的是西北工业大学的学生或教师分享的一份C++编程语言在解决Programming Online Judge(POJ)平台上的题目时的解答集合。POJ是一个在线编程竞赛平台,主要面向大学生和编程爱好者...
《田忌赛马:POJ 2287 贪心解法解析》 在计算机科学领域,算法是解决问题的核心。"田忌赛马"这个题目来源于古代中国的一个著名故事,而在这个故事的基础上,被引入到了编程竞赛的场景中。POJ(Programming Online ...
在这种情况下,"ai3717"可能是C++、Java或其他编程语言的源代码文件,包含了作者对POJ3717问题的解决方案。 由于没有给出具体的题目内容和代码,我们无法深入讨论解题策略或算法实现。不过,一般来说,解决POJ上的...
根据【压缩包子文件的文件名称列表】:“北大题”,我们可以推测这个压缩包内包含的是一系列与北京大学POJ题库相关的题目解法代码。每个文件可能对应一个具体的题目,文件名可能是题目的编号或者题目描述的一部分。 ...
北京大学的POJ题目解题代码集合是一份宝贵的资源,它涵盖了ACM(国际大学生程序设计竞赛)中的许多问题,旨在帮助学生和编程爱好者提升算法理解与编程技能。POJ(Problem Set for Online Judges)是中国最早的在线...
2. "POJ1010-STAMPS.doc":这是一个文档文件,很可能包含了对问题的详细解释、解题思路、算法流程图、时间复杂度分析等内容,对于学习和理解这个问题的解法非常有帮助。 综合以上信息,我们可以推断,"POJ1010-...
"POJ 1000-1200大部分资源代码"是一个专门为初学者准备的宝藏库,其中包含了C++和JAVA两种编程语言的源码。POJ,全称是Programming Online Judge,是一个知名的在线编程竞赛平台,它为程序员提供了丰富的编程题目,...
【压缩包子文件的文件名称列表】中,"POJ2531-Network Saboteur.cpp"是用C++编写的源代码文件,包含了实现解题逻辑的程序;"POJ2531-Network Saboteur.doc"可能是一个文档文件,详细解释了解题思路、算法描述或者...
【压缩包子文件的文件名称列表】中,"POJ3080-Blue Jeans.cpp" 是提交给POJ平台的AC代码,可能包含了上述的动态规划解法,使用C++语言实现。"POJ3080-Blue Jeans.doc" 可能是解题报告文档,详细解释了解题过程和思路...
POJ是一个以C、C++和Java为主要语言的在线编程竞赛平台,它提供了各种算法和逻辑思维的练习题目,旨在提升程序员的编程能力和解决问题的能力。 描述中的“网上收集”表明这个压缩包里的代码是从网络上搜集而来,...
首先,我们需要理解POJ(北大在线评测系统)是一个供程序员练习和提交代码的平台,主要支持C、C++和Java语言。它提供各种不同难度级别的编程题目,帮助用户提升算法和编程能力。 题目“Check the difficulty of ...
ACM竞赛旨在提升大学生的算法设计和编程能力,因此题目的难度和复杂性较高,涉及的编程语言通常包括C、C++、Java等。这个描述中的"来源网络"和"自己整理一部分"说明了题目的收集方式,既包括网络上公开的资源,也有...
【压缩包子文件的文件名称列表】:POJ1338 这个文件可能是包含解题代码的源文件,通常使用的编程语言可能有C++、Java、Python等。解题代码会清晰地展示如何根据题目要求构建算法,实现数据结构,以及如何优化时间...
5. 思路拓展:讨论可能的优化方法,或者对比不同解法的优缺点,帮助读者深化对问题本质的理解。 通过阅读《北大ACM题解》,你可以学习到如何分析问题,选择合适的算法,以及编写高效的代码。这将对你在ACM竞赛中的...
在"poj.rar"这个压缩包中,包含的是用户完成的POJ题目源代码,可能是用C、C++或Java等编程语言编写的。 【描述】"我最近做的几个poj题目源代码,可能比较简单" 暗示了这些代码是作者近期解决的一些基础或入门级别的...
【压缩包子文件的文件名称列表】中的"POJ1083-Moving Tables.cpp"是C++语言编写的源代码文件,包含了解决该问题的算法实现。".cpp"扩展名表明这是一段C++代码,可能使用了STL(Standard Template Library)等C++特性...
它不仅包含了丰富的ACM题目的C++解答代码,还有针对Java语言在POJ平台上的应用指导,以及对优秀编程思路和算法策略的总结。通过对这些高质量的编程代码和总结的研习,我们不仅能提高编程水平,更能在ACM编程竞赛中...
1. "POJ1716-Integer Intervals【Difference Constraints】.cpp":这可能是基于差分约束系统理论的C++代码实现,它可能采用了动态规划或者线性规划的方法来解决问题。 2. "POJ1716-Integer Intervals【Greed】.cpp...
4. **编程实践**:通过"poj_3310.txt"中的代码,我们可以看到问题的代码实现,这可能涉及C++、Java或Python等常见编程语言,学习如何将算法转化为实际的程序。 5. **代码优化**:作者可能会分享代码优化的技巧,...