網站首頁 編程語言 正文
題目描述
明明同學最近迷上了偵探漫畫《柯南》并沉醉于推理游戲之中,于是他召集了一群同學玩推理游戲。游戲的內容是這樣的,明明的同學們先商量好由其中的一個人充當罪犯(在明明不知情的情況下),明明的任務就是找出這個罪犯。接著,明明逐個詢問每一個同學,被詢問者可能會說:
證詞內容:
I am guilty.
I am not guilty.
XXX is guilty.
XXX is not guilty.
Today is XXX
證詞含義:
我是罪犯
我不是罪犯
xxx 是罪犯( xxx 表示某個同學的名字)
xxx 不是罪犯
今天是xxx ( xxx 表示星期幾,是 Monday Tuesday wednesday Thursday Fnday Saturday 其中之一)?
證詞中出現的其他話,都不列入邏輯推理的內容。明明所知道的是,他的同學中有 N 個人始終說假話,其余的人始終說真。現在,明明需要你幫助他從他同學的話中推斷出誰是真正的兇手,請記住,兇手只有一個!
輸入描述
輸入若干行。
第一行有三個整數,M(1 ≤ M ≤ 20)、N(1 ≤ N ≤ M)和P(1 ≤ P ≤ 100);M 是參加游戲的明明的同學數,N 是其中始終說謊的人數,P 是證言的總數。
接下來 M 行,每行是明明的一個同學的名字(英文字母組成,沒有主格,全部大寫)。
往后有 P 行,每行開始是某個同學的名宇,緊跟著一個冒號和一個空格,后面是一句證詞,符合前表中所列格式。證詞每行不會超過 250 個字符。
輸入中不會出現連續的兩個空格,而且每行開頭和結尾也沒有空格。
輸出描述
如果你的程序能確定誰是罪犯,則輸出他的名字;如果程序判斷出不止一個人可能是罪犯,則輸出 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
最大運行內存:128M
算法實現
/* 大模擬問題 */ #include <bits/stdc++.h> using namespace std; //m:總人數 n:始終說謊人數 p:說話的總數 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函數標記一個人說話真假 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; //說假話的人數 int no = 0; //不清楚真假的的人數 for (int i = 1; i <= m; i++) { if (judge[i] == -1) //假 cnt++; if (judge[i] == 0) //不清楚 no++; } //如果出現Impossible的情況,err = 1,出現矛盾 //如果cnt<=n<=cnt+no,即假設合理 if (!err && cnt <= n && cnt + no >= n) { if (nx && nx != px) { //如果出現了兩個合理的罪犯 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
相關推薦
- 2023-02-17 linux?命令中的大于號、小于號的作用及代表的意思_linux shell
- 2022-03-16 Linux環境下安裝nginx教程_nginx
- 2022-03-16 開發者必備Docker命令小結_docker
- 2024-03-04 新版ECharts實現“暫無數據”的完美解決方案
- 2022-04-07 C#實現Socket服務器及多客戶端連接的方式_C#教程
- 2022-04-26 C#元組類型ValueTuple用法詳解_實用技巧
- 2023-04-08 C語言字符串左旋的兩種實現方法_C 語言
- 2023-10-31 SpringBoot手動獲取實例
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支