網(wǎng)站首頁 編程語言 正文
題目描述
明明同學(xué)最近迷上了偵探漫畫《柯南》并沉醉于推理游戲之中,于是他召集了一群同學(xué)玩推理游戲。游戲的內(nèi)容是這樣的,明明的同學(xué)們先商量好由其中的一個人充當罪犯(在明明不知情的情況下),明明的任務(wù)就是找出這個罪犯。接著,明明逐個詢問每一個同學(xué),被詢問者可能會說:
證詞內(nèi)容:
I am guilty.
I am not guilty.
XXX is guilty.
XXX is not guilty.
Today is XXX
證詞含義:
我是罪犯
我不是罪犯
xxx 是罪犯( xxx 表示某個同學(xué)的名字)
xxx 不是罪犯
今天是xxx ( xxx 表示星期幾,是 Monday Tuesday wednesday Thursday Fnday Saturday 其中之一)?
證詞中出現(xiàn)的其他話,都不列入邏輯推理的內(nèi)容。明明所知道的是,他的同學(xué)中有 N 個人始終說假話,其余的人始終說真。現(xiàn)在,明明需要你幫助他從他同學(xué)的話中推斷出誰是真正的兇手,請記住,兇手只有一個!
輸入描述
輸入若干行。
第一行有三個整數(shù),M(1 ≤ M ≤ 20)、N(1 ≤ N ≤ M)和P(1 ≤ P ≤ 100);M 是參加游戲的明明的同學(xué)數(shù),N 是其中始終說謊的人數(shù),P 是證言的總數(shù)。
接下來 M 行,每行是明明的一個同學(xué)的名字(英文字母組成,沒有主格,全部大寫)。
往后有 P 行,每行開始是某個同學(xué)的名宇,緊跟著一個冒號和一個空格,后面是一句證詞,符合前表中所列格式。證詞每行不會超過 250 個字符。
輸入中不會出現(xiàn)連續(xù)的兩個空格,而且每行開頭和結(jié)尾也沒有空格。
輸出描述
如果你的程序能確定誰是罪犯,則輸出他的名字;如果程序判斷出不止一個人可能是罪犯,則輸出 Cannot Determine;如果程序判斷出沒有人可能成為罪犯,則輸出 Impossible。
輸入輸出樣例
輸入
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??
輸出
MIKE
運行限制
最大運行時間:1s
最大運行內(nèi)存:128M
算法實現(xiàn)
/* 大模擬問題 */ #include <bits/stdc++.h> using namespace std; //m:總?cè)藬?shù) n:始終說謊人數(shù) p:說話的總數(shù) int m, n, p; //judge[i]:第i句話是真是假,真1假-1不清楚0 w[i]:第i局話是編號多少的的人說的 int judge[21], w[200]; //err:矛盾標記 nx:當前可能的罪犯 int err, nx; //name[i]:所有人名字(編號為1~m) say[i]:所有人說的話 day[i]:所有星期幾名字 string name[100], say[200]; string day[10] = {"0", "Today is Sunday.", "Today is Monday.", "Today is Tuesday.", "Today is Wednesday.", "Today is Thursday.", "Today is Friday.", "Today is Saturday.", }; //sset函數(shù)標記一個人說話真假 void sset(int who, int x) { if (judge[who] == -x) err = 1; //如果一個人既說真話又說假話,則矛盾 else judge[who] = x; } int main() { cin >> m >> n >> p; for (int i = 1; i <= m; i++) { cin >> name[i]; } for (int i = 1; i <= p; i++) { string nm; cin >> nm; //輸入說這句話人的名字 nm.erase(nm.end() - 1); //刪除nm中冒號,便于判斷這句話編號多少的的人說的 for (int j = 1; j <= m; j++) { if (name[j] == nm) w[i] = j; } getline(cin, say[i]); say[i].erase(say[i].begin()); //刪除say[i]中的起始空格 } for (int td = 1; td <= 7; td++) { //暴力枚舉今天是星期幾 for (int px = 1; px <= m; px++) { //暴力枚舉罪犯編號是幾號 err = 0; //清除標記 memset(judge, 0, sizeof(judge)); //初始化為不清楚真假 //依次判斷每一句說的話 for (int i = 1; i <= p; i++) { int who = w[i]; //說這句話人的編號 //如果一個人是罪犯,并且說自己是罪犯,則說的就是真話,否則就是假話 if (say[i] == "I am guilty.") sset(who, px == who ? 1 : -1); //如果一個人不是罪犯,并且說自己不是罪犯,則說的就是真話,否則就是假話 if (say[i] == "I am not guilty.") sset(who, px != who ? 1 : -1); //如果一個人說今天是星期幾,說對了就是真話,說錯了就是假話 for (int j = 1; j <= 7; j++) { if (say[i] == day[j]) sset(who, j == td ? 1 : -1); } //如果一個人說其他人不是罪犯,說對了就是真話,說錯了就是假話 for (int j = 1; j <= m; j++) { if (say[i] == name[j] + " is guilty.") sset(who, j == px ? 1 : -1); if (say[i] == name[j] + " is not guilty.") sset(who, j != px ? 1 : -1); } } int cnt = 0; //說假話的人數(shù) int no = 0; //不清楚真假的的人數(shù) for (int i = 1; i <= m; i++) { if (judge[i] == -1) //假 cnt++; if (judge[i] == 0) //不清楚 no++; } //如果出現(xiàn)Impossible的情況,err = 1,出現(xiàn)矛盾 //如果cnt<=n<=cnt+no,即假設(shè)合理 if (!err && cnt <= n && cnt + no >= n) { if (nx && nx != px) { //如果出現(xiàn)了兩個合理的罪犯 cout << "Cannot Determine"; return 0; } else { nx = px; } } } } if (!nx) cout << "Impossible"; else cout << name[nx]; return 0; }
原文鏈接:https://blog.csdn.net/Hello_world_n/article/details/121630843
相關(guān)推薦
- 2022-07-06 python中csv文件創(chuàng)建、讀取及修改等操作實例_python
- 2022-08-26 pandas應(yīng)用實例之pivot函數(shù)詳解_python
- 2022-06-21 詳解C#中檢查null的語法糖_C#教程
- 2022-06-17 一文輕松了解ASP.NET與ASP.NET?Core多環(huán)境配置對比_實用技巧
- 2022-09-08 pytorch?tensor內(nèi)所有元素相乘實例_python
- 2024-07-18 Spring Security之基于方法配置權(quán)限
- 2022-12-04 Python中的配對函數(shù)zip()解讀_python
- 2022-07-26 面向?qū)ο驩OP基礎(chǔ)理解
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細win安裝深度學(xué)習(xí)環(huán)境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區(qū)別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯誤:Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊列,發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支