题目描述
一个人设定一组四码的数字作为谜底，另一方猜。
每猜一个数，出数者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。
其中X表示位置正确的数的个数（数字正确且位置正确），而Y表示数字正确而位置不对的数的个数。
例如，当谜底为8123，而猜谜者猜1052时，出题者必须提示0A2B。
例如，当谜底为5637，而猜谜者才4931时，出题者必须提示1A0B。
当前已知N组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出NA。
输入描述
第一行输入一个正整数，0＜N ＜ 100。
接下来N行，每一行包含一个猜测的数字与提示结果。
输出描述
输出最后的答案，答案不确定则输出NA。
用例
整体流程
开始
↓
读取输入数据
↓
预处理：剪枝缩小搜索空间
↓
生成候选答案
↓
验证候选答案
↓
输出唯一答案或NA详细逻辑说明
1. 数据读取阶段
读取猜测次数N
读取N组(猜测数字, 提示结果)
2. 预处理阶段（剪枝优化）
为谜底的4个位置分别建立可能数字的集合
利用已知信息排除不可能的数字：
如果某位A=0，该位置不可能是猜测的对应数字
如果B=0，所有位置都不包含猜测中的任何数字
3. 候选生成阶段
在剪枝后的数字范围内，生成所有可能的4位数组合
4. 验证阶段
对每个候选答案，检查是否与所有已知的猜测结果一致
使用XAYB规则验证每个猜测
5. 结果输出阶段
如果只有一个有效答案，输出该答案
如果有多个或没有有效答案，输出"NA"
算法实现
def main():
# 读取输入数据
n, guesses = read_input()
# 预处理：获取每位可能的数字
possible_digits = preprocess_possible_digits(guesses)
# 生成候选答案
candidate_answers = generate_candidates(possible_digits)
# 验证候选答案
valid_answers = validate_candidates(candidate_answers, guesses)
# 输出最终结果
output_result(valid_answers)
def read_input():
"""读取输入数据"""
n = int(input())
guesses = []
for _ in range(n):
guess, result = input().split()
guesses.append((guess, result))
return n, guesses
def calculate_guess_result(guess, answer):
"""
计算猜测结果：XAYB
X: 数字和位置都正确的个数
Y: 数字正确但位置不对的个数
"""
a_count = 0 # 数字和位置都正确
b_count = 0 # 数字正确但位置不对
# 统计数字出现次数（排除位置正确的数字）
guess_count = [0] * 10
answer_count = [0] * 10
for i in range(4):
g_digit = int(guess[i])
a_digit = int(answer[i])
if g_digit == a_digit:
a_count += 1
else:
guess_count[g_digit] += 1
answer_count[a_digit] += 1
# 计算B：数字正确但位置不对的个数
for digit in range(10):
b_count += min(guess_count[digit], answer_count[digit])
return f"{a_count}A{b_count}B"
def preprocess_possible_digits(guesses):
"""
预处理：根据猜测结果缩小每位可能的数字范围
返回：列表，包含4个集合，每个集合是对应位可能的数字
"""
# 初始化：每位都可能是0-9
possible_digits = [set(range(10)) for _ in range(4)]
for guess, result in guesses:
guess_num = guess
countA = int(result[0])
countB = int(result[2])
# 剪枝逻辑
if countA == 0:
# 如果A=0，说明每位上的数字都不正确
for i in range(4):
digit = int(guess_num[i])
if countB == 0:
# 如果B=0，说明所有数字都不在答案中
for j in range(4):
possible_digits[j].discard(digit)
else:
# 该位置不可能是这个数字
possible_digits[i].discard(digit)
return possible_digits
def generate_candidates(possible_digits):
"""根据可能的数字生成所有候选答案"""
candidates = []
for d1 in possible_digits[0]:
for d2 in possible_digits[1]:
for d3 in possible_digits[2]:
for d4 in possible_digits[3]:
candidate = f"{d1}{d2}{d3}{d4}"
candidates.append(candidate)
return candidates
def validate_candidates(candidates, guesses):
"""验证候选答案是否符合所有猜测结果"""
valid_answers = []
for candidate in candidates:
if is_candidate_valid(candidate, guesses):
valid_answers.append(candidate)
return valid_answers
def is_candidate_valid(candidate, guesses):
"""检查单个候选答案是否有效"""
for guess, expected_result in guesses:
actual_result = calculate_guess_result(guess, candidate)
if actual_result != expected_result:
return False
return True
def output_result(valid_answers):
"""输出最终结果"""
if len(valid_answers) == 1:
print(valid_answers[0])
else:
print("NA")
if __name__ == "__main__":
main()