哪个网站可以做思维导图,网络营销团队,怎样做才能让百度搜到网站产品,wordpress配置163邮箱题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中#xff0c;于是他召集了一群同学玩推理游戏。游戏的内容是这样的#xff0c;明明的同学们先商量好由其中的一个人充当罪犯#xff08;在明明不知情的情况下#xff09;#xff0c;明明的任务就是找出这…题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中于是他召集了一群同学玩推理游戏。游戏的内容是这样的明明的同学们先商量好由其中的一个人充当罪犯在明明不知情的情况下明明的任务就是找出这个罪犯。接着明明逐个询问每一个同学被询问者可能会说 证词中出现的其他话都不列入逻辑推理的内容。
明明所知道的是他的同学中有 N 个人始终说假话其余的人始终说真。
现在明明需要你帮助他从他同学的话中推断出谁是真正的罪犯请记住罪犯只有一个
输入格式
输入由若干行组成。
第一行有三个整数M, N 和P。M是参加游戏的明明的同学数N是其中始终说谎的人数P是证言的总数。
接下来M行每行是明明的一个同学的名字英文字母组成没有空格全部大写。
往后有P 行每行开始是某个同学的名宇紧跟着一个冒号和一个空格后面是一句证词符合前表中所列格式。证词每行不会超过 250个字符。
输入中不会出现连续的两个空格而且每行开头和结尾也没有空格。
输出格式
如果你的程序能确定谁是罪犯则输出他的名字如果程序判断出不止一个人可能是罪犯则输出 Cannot Determine如果程序判断出没有人可能成为罪犯则输出 Impossible。
输入输出样例 说明/提示
对于 100% 数据满足1≤M≤200≤N≤M1≤P≤100。
【题目来源】
NOIP 2003提高组第二题
解题思路
单凭一条条证言判断某人是说真话还是假话是很难的但因为只有一名罪犯所以枚举每位同学假设某同学是罪犯来判断各条证言是否成立来判定某人是说真话还是假话
另外证言中有说今天是星期几但不能确定当天是星期几无法直接判定是说真话还是假话所以也要枚举星期然后根据n个人是始终说谎的来判断说谎的同学。
每个句子有三种情况真话、假话、废话。最终只要假话数量≤n≤假话数量 废话数量那么说谎的同学就有可能有n个。
正确理解题目
只有以下五种句式的证言是有效证言其余都是无效证言(废话)。
I am guilty.
I am not guilty.
XXX is guilty.
XXX is not guilty.
Today is XXX.
证词的含义
说真话、说假话与是否是罪犯没有任何关系。XXX指认YYY是罪犯若是真话YYY就是罪犯若是假话YYY不是罪犯罪犯是除YYY之外的某一个人。XXX指认YYY不是罪犯若是真话YYY不是罪犯罪犯是除YYY之外的某一个人若是假话YYY就是罪犯。今天是星期几用以辅助判断证人说的是真话还是假话。如两个人说的不是同个星期几那么其中至少有人说假话。
注意题目中说“N个人始终说假话其余的人始终说真”意思是一个人的证词要么全部为真要么全部为假。注意不在上述类型的证词可以算是真话也可以算是假话。因为有“废话”存在说真话人数不超过M-N说假话人数不超过N。
推理算法
单从证词去推理是不可行的因为不知道谁说了真话、谁说了假话不能把真话、假话放在一起推理。
思路就是枚举某人是罪犯再枚举今天是星期几然后就可以判断每个证言是说真话还是假话。
每次枚举时标记每个人说的是什么话如果一个人既说真话又说假话那就说明你的假设不成立与题目矛盾直接跳过此种情况。
如找不到罪犯则输出 Impossible如果程序判断出罪犯超过1人则输出Cannot Determine。
时间复杂度分析:
依次枚举可能的罪犯、星期几以及证言句子所以总时间复杂度是O(7mp)其中m是总人数p是总证言数。
完整代码
weekdays [Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday]def parse(s): # 解析证言句子返回“某人”说“某某人”是/不是罪犯或今天是星期几name, test s.split(: , 1)if test I am guilty: # 某人说自己是罪犯return (name, name, yes)elif test I am not guilty: # 某人说自己不是罪犯return (name, name, no)elif test.endswith( is guilty): # 检测是否以 is guilty结尾obj test.split( )[0] # 某人说某某人是罪犯return (name, obj, yes)elif test.endswith( is not guilty): # 检测是否以 is not guilty结尾obj test.split( )[0] # 某人说某某人不是罪犯return (name, obj, no)elif test.startswith(Today is ):day test.split( is )[1] # 某人说今天是星期几return (name, None, day, day)else: # 无效证言return (name, None, None)def analyze(testimony, guilty, weekday):if testimony[2] yes:return guilty testimony[1]elif testimony[2] no:return guilty ! testimony[1]elif testimony[2] day:return weekday testimony[3]m, n, p [int(i) for i in input().split()]
names [input() for i in range(m)] # 嫌疑犯名单
testimonys [parse(input()[:-1]) for i in range(p)] # 证言去除尾部句点(.)suspects set() # 嫌疑犯(去重)
for guilty in names: # 枚举罪犯是谁for weekday in weekdays: # 枚举今天是星期几judge {}impossbile Falsefor testimony in testimonys: # 枚举各证言测试在这种情况下是否为真speaker testimony[0]result analyze(testimony, guilty, weekday)if speaker not in judge and result ! None:judge[speaker] resultelif speaker in judge and result ! None and result ! judge[speaker]:judge[speaker] rejectimpossbile Truebreakif not impossbile and list(judge.values()).count(True) m-n and list(judge.values()).count(False) n:suspects.add(guilty)if len(suspects) 0: # 无解print(Impossible)
elif len(suspects) 1: # 多解print(Cannot Determine)
else:print(list(suspects)[0])
运行结果
