題目描述

一個人設定一組四碼的數字作為謎底，另一方猜。

每猜一個數，出數者就要根據這個數字給出提示，提示以XAYB形式呈現，直到猜中位置。

其中X表示位置正確的數的個數（數字正確且位置正確），而Y表示數字正確而位置不對的數的個數。

例如，當謎底為8123，而猜謎者猜1052時，出題者必須提示0A2B。

例如，當謎底為5637，而猜謎者才4931時，出題者必須提示1A0B。

當前已知N組猜謎者猜的數字與提示，如果答案確定，請輸出答案，不確定則輸出NA。

輸入描述
第一行輸入一個正整數，0＜N ＜ 100。

接下來N行，每一行包含一個猜測的數字與提示結果。

輸出描述
輸出最后的答案，答案不確定則輸出NA。

用例

輸入	6 4815 1A1B 5716 0A1B 7842 0A1B 4901 0A0B 8585 3A0B 8555 2A1B
輸出	3585
說明	無

猜數字游戲解題思路（確定謎底數字）

一、核心解題思路

問題分析
題目要求根據多組猜測和對應的XAYB提示（X表示數字和位置都正確的個數，Y表示數字正確但位置不對的個數），確定唯一的四位數謎底：

1. 輸入包含N組（猜測數字, XAYB提示）
2. 謎底是四位數（取值范圍1000~9999）
3. 需要驗證候選謎底是否滿足所有提示
4. 輸出規則：

• 唯一滿足條件的謎底 → 輸出該數字
• 多個滿足條件 → 輸出"NA"
• 無滿足條件 → 輸出"NA"

關鍵策略

1. 候選謎底生成：遍歷1000~9999所有四位數
2. 提示驗證：對每個候選謎底檢查是否滿足所有XAYB提示
3. XAYB計算：

• 計算數字和位置都正確的數量（A）
• 計算數字正確但位置錯誤的數量（B）

4. 結果篩選：記錄所有滿足條件的謎底，根據數量決定輸出

二、完整代碼實現

def calculate_A_B(candidate, guess):"""計算候選謎底與猜測的A和B值"""candidate_str = str(candidate)guess_str = str(guess)# 計算A（位置和數字都正確）A = 0for i in range(4):if candidate_str[i] == guess_str[i]:A += 1# 計算B（數字正確但位置錯誤）candidate_digits = {}guess_digits = {}# 統計未匹配位置的數字頻率for i in range(4):if candidate_str[i] != guess_str[i]:candidate_digits[candidate_str[i]] = candidate_digits.get(candidate_str[i], 0) + 1guess_digits[guess_str[i]] = guess_digits.get(guess_str[i], 0) + 1B = 0for digit in guess_digits:if digit in candidate_digits:B += min(guess_digits[digit], candidate_digits[digit])return A, Bdef main():import sysdata = sys.stdin.read().splitlines()if not data:  # 處理空輸入print("NA")returnn = int(data[0])guesses = []# 解析輸入數據for i in range(1, n + 1):if i >= len(data):  # 確保數據行存在breakparts = data[i].split()if len(parts) < 2:  # 確保有猜測和提示continueguess_num = parts[0]hint = parts[1]# 確保提示格式正確if len(hint) != 3 or hint[1] != 'A' or not hint[0].isdigit() or not hint[2].isdigit():continue# 提取A和B的值A_val = int(hint[0])B_val = int(hint[2])guesses.append((guess_num, A_val, B_val))solutions = []# 遍歷所有可能的四位數候選for candidate in range(1000, 10000):candidate_str = str(candidate)valid = True# 檢查是否滿足所有猜測條件for guess_num, A_val, B_val in guesses:A, B = calculate_A_B(candidate_str, guess_num)if A != A_val or B != B_val:valid = Falsebreakif valid:solutions.append(candidate_str)# 輸出結果if len(solutions) == 0:print("NA")elif len(solutions) == 1:print(solutions[0])else:print("NA")if __name__ == "__main__":main()

三、算法原理解析

1. A值計算

A = 0
for i in range(4):
if candidate[i] == guess[i]:
A += 1

• 直接比較相同位置的數字
• 完全匹配時計數增加

2. B值計算

# 統計未匹配位置的數字頻率
for i in range(4):
if candidate[i] != guess[i]:
candidate_digits[candidate[i]] += 1
guess_digits[guess[i]] += 1# 計算共同數字的最小頻率
B = 0
for digit in guess_digits:
if digit in candidate_digits:
B += min(guess_digits[digit], candidate_digits[digit])

• 排除已匹配位置（A值位置）
• 統計剩余數字的出現頻率
• 取相同數字的最小頻率作為B值

3. 候選驗證
對每個候選謎底：

1. 遍歷所有猜測提示
2. 計算候選謎底與當前猜測的A、B值
3. 與提示的A、B值比對
4. 任意提示不匹配即淘汰該候選

四、示例解析

輸入示例：

6
4815 1A1B
5716 0A1B
7842 0A1B
4901 0A0B
8585 3A0B
8555 2A1B

驗證過程（以候選3585為例）：

1. 4815 → 計算：A=1（第4位5匹配），B=1（8在候選第3位） → 匹配1A1B
2. 5716 → 計算：A=0，B=1（5在候選第2,4位） → 匹配0A1B
3. 7842 → 計算：A=0，B=1（8在候選第3位） → 匹配0A1B
4. 4901 → 計算：A=0，B=0 → 匹配0A0B
5. 8585 → 計算：

• A=3（第2位5、第3位8、第4位5匹配）
• B=0 → 匹配3A0B

6. 8555 → 計算：

• A=2（第2位5、第4位5匹配）
• B=1（8在候選第3位） → 匹配2A1B

結果輸出：3585

圖解說明：

候選謎底：3 5 8 5猜測4815：
3≠4, 5≠8, 8≠1, 5=5 → A=1
未匹配：候選[3,5,8], 猜測[4,8,1] → 共同數字8 → B=1猜測5716：
3≠5, 5=5（匹配A不參與B）, 8≠1, 5≠6 → A=0
未匹配：候選[3,8,5], 猜測[7,1,6] → 無共同數字 → B=0（但實際計算有5？注意匹配的5已排除）
修正：候選未匹配[3,8,5]中的5在候選第4位（未匹配位置），猜測中未匹配的7,1,6 → 無共同 → B=0？
但題目提示0A1B → 矛盾？重新計算5716：
候選：3 5 8 5
猜測：5 7 1 6
位置1：3≠5 → 未匹配
位置2：5=5 → 匹配（A=1？但題目提示0A）
位置3：8≠1 → 未匹配
位置4：5≠6 → 未匹配
因此A=1（位置2）≠0 → 不符合0A1B問題：題目實際輸入是5716 0A1B，但候選3585在位置2匹配（5），A應該為1但實際運行結果3585符合所有條件，說明題目中提示是準確的。重新檢查題目："第二組：5716 -> 0A1B
3 vs 5 -> 不同
5 vs 7 -> 不同
8 vs 1 -> 不同
5 vs 6 -> 不同 -> A=0
候選未匹配位置：3,5,8,5 （注意：謎底3585，所以未匹配位置是全部：3,5,8,5，頻率：3:1,5:2,8:1）
猜測未匹配位置：5,7,1,6
5：在頻率表中（出現2次），所以B=1，然后頻率表中5變成1次（5:1）。
7：不在頻率表中，跳過。
1：不在，跳過。
6：不在，跳過。
所以B=1，提示0A1B符合。"關鍵點：位置2的5在候選中是5，在猜測中也是5，但為什么算未匹配？
因為題目要求"位置正確"才計入A，位置2的候選是5，猜測是7？實際猜測5716：
位置1：5（猜測） vs 3（候選） → 不匹配
位置2：7（猜測） vs 5（候選） → 不匹配
位置3：1（猜測） vs 8（候選） → 不匹配
位置4：6（猜測） vs 5（候選） → 不匹配
所以A=0，不是1先前錯誤認為猜測是"5716"對應位置2是5，實際是7結論：3585滿足所有條件

五、總結

算法特點：

1. 暴力枚舉：遍歷所有可能四位數候選（1000~9999）
2. 精確驗證：通過A/B值計算嚴格匹配提示
3. 高效處理：

• 時間復雜度：9000×N×4 ≈ 3.6×10?（N≤100）
• 空間復雜度：O(1)

4. 魯棒性強：正確處理重復數字場景

關鍵要點：

• A值計算：位置和數字完全匹配
• B值計算：
• 排除已匹配位置
• 頻率統計共同數字
• 取最小值保證不重復計數
• 結果篩選：
• 唯一解 → 輸出數字
• 多解/無解 → 輸出"NA"

應用場景：

• 猜數字游戲AI
• 密碼破解系統
• 數據驗證工具
• 游戲測試自動化

該解法通過系統枚舉和精確驗證，高效解決了猜數字游戲的謎底確定問題，能正確處理各種邊界情況和重復數字場景。