猜数字

题目描述

一个人设定一组四码的数字作为谜底，另一方猜。

每猜一个数，出数者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。

其中X表示位置正确的数的个数（数字正确且位置正确），而Y表示数字正确而位置不对的数的个数。

例如，当谜底为8123，而猜谜者猜1052时，出题者必须提示0A2B。

例如，当谜底为5637，而猜谜者才4931时，出题者必须提示1A0B。

当前已知N组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出NA。

输入描述

第一行输入一个正整数，0＜N ＜ 100。

接下来N行，每一行包含一个猜测的数字与提示结果。

输出描述

输出最后的答案，答案不确定则输出NA。

示例1

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

输出：
3585

题解

这道题属于 暴力搜索（Brute Force） 结合 模拟（Simulation） 的算法题。我们需要枚举所有可能的4位数，并验证每个数是否符合给定的所有提示条件。

解题思路

输入处理：读取输入的猜测记录（数字和对应的XAYB提示）。

验证函数：编写一个 check 函数，判断某个候选答案是否符合某条猜测记录的提示。

计算数字和位置都正确的数量（X）。

计算数字正确但位置不对的数量（Y）。

枚举所有可能的4位数：从 0000 到 9999，检查每个数是否满足所有给定的提示记录。

输出结果：如果只有一个候选答案满足所有条件，输出它；否则输出 NA。

C++

#include <bits/stdc++.h>

using namespace std;

bool check(const string& guess, const string& answer, const string& expectResult) {
    // 数字正确且位置正确个数
    int x = 0;
    for (int i = 0; i < 4; i++) {
        if (guess[i] == answer[i]) x++;
    }

    // 数字正确而位置不对的数的个数
    map<char, int> cnt1, cnt2;
    for (char c : guess) cnt1[c]++;
    for (char c : answer) cnt2[c]++;
    int y = 0;
    for (const auto& [k, v] : cnt1) {
        y += min(v, cnt2[k]);;
    }
    y -= x;

    string actualResult = to_string(x) + "A" + to_string(y) + "B";
    return actualResult == expectResult;
}

int main() {
    int n;
    cin >> n;
    cin.ignore();  // 忽略换行符

    vector<pair<string, string>> logs;
    for (int i = 0; i < n; i++) {
        string guess, result;
        cin >> guess >> result;
        logs.emplace_back(guess, result);
    }

    vector<string> candidates;
    for (int x = 0; x < 10000; x++) {
        stringstream ss;
        ss << setw(4) << setfill('0') << x;
        string answer = ss.str();

        bool allMatch = all_of(logs.begin(), logs.end(), [answer](const auto& log) { return check(log.first, answer, log.second);});
        if (allMatch) {
            candidates.push_back(answer);
        }
    }

    if (candidates.size() == 1) {
        cout << candidates[0] << endl;
    } else {
        cout << "NA" << endl;
    }

    return 0;
}