🔗 UVA-340 Master-Mind Hints

tags: `模擬(Simulation)` `計數(Counter)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

在 ZeroJudge 上的測資數字是包含 $0$ 的，而不是題目敘述的 $[1, 9]$ 之間的數字，且必須要全為 $0$ 才會結束，與原本題目敘述不同，需要注意一下。

題意

你正在和朋友玩猜數字遊戲，遊戲規則如下：

你寫下一個秘密數字，並要求你的朋友猜出這個數字是什麼。當你的朋友猜測時，你會提供一個包含下述信息的提示：
- 猜測數字中有多少位屬於數字和確切位置都猜對了（稱為得到一個 $A$ ）。
- 有多少位屬於數字猜對了但是位置不對（稱為得到一個 $B$ ）。
給定一個秘密數字 $secret$ 和朋友猜測的數字 $guess$ ，請你根據規則輸出 $A$ 和 $B$ 的數量。
請注意，秘密數字和朋友猜測的數字可能包含重複的數字。

思路：模擬(Simulation) + 計數(Counter)

遍歷 $secret$ 和 $guess$ ，計算 $A$ 的數量，即 $secret[i] == guess[i]$ 的數量；若 $secret[i] \neq guess[i]$ ，則將 $secret[i]$ 和 $guess[i]$ 的數量分別記錄在 $cnt_s$ 和 $cnt_g$ 中，其中 $cnt_s$ 和 $cnt_g$ 分別為 $secret$ 和 $guess$ 中每個數字的出現次數。

若 $cnt_s[i] < cnt_g[i]$ 則代表 $secret$ 中的 $i$ 出現次數小於 $guess$ 中的 $i$ 出現次數，則對於 $i$ 的 $B$ 數量為 $cnt_s[i]$ ；否則對於 $i$ 的 $B$ 數量為 $cnt_g[i]$ 。即對於每個數字 $i$ ，取 $cnt_s[i]$ 和 $cnt_g[i]$ 的最小值。將所有數字的 $B$ 數量相加即為 $cows$ 的數量。

複雜度分析

時間複雜度： $O(n)$ ，其中 $n$ 為 $secret$ 和 $guess$ 的長度。
空間複雜度： $O(n)$ ，其中輸入使用 $O(n)$ 空間，計數使用 $O(10)$ 空間。

from collections import Counter
kase = 1
while True:
    n = int(input())
    if n == 0:
        break
    print(f"Game {kase}:")
    kase += 1
    s = list(map(int, input().split())) # secret
    cnt_s0 = Counter(s)
    while True:
        g = list(map(int, input().split())) # guess
        if all(x == 0 for x in g):
            break
        A = 0
        cnt_s = cnt_s0.copy()
        cnt_g = Counter(g)
        for i in range(n):
            if s[i] == g[i]:
                A += 1
                cnt_s[s[i]] -= 1
                cnt_g[g[i]] -= 1
        B = sum(min(cnt_s[k], cnt_g[k]) for k in cnt_g)
        print(f"    ({A},{B})")

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int kase=1, n, A, B;
    int s[N], g[N], cnt_s0[10], cnt_s[10], cnt_g[10];
    while (cin >> n && n) {
        cout << "Game " << kase++ << ":" << endl;
        for (int i = 0; i < n; i++) cin >> s[i]; // read secret
        memset(cnt_s0, 0, sizeof(cnt_s0));
        for (int i = 0; i < n; i++) cnt_s0[s[i]]++;
        while (1) {
            for (int i = 0; i < n; i++) cin >> g[i]; // read guess
            bool flag = true; // check if all elements are 0
            for (int i = 0; i < n; i++) if (g[i] != 0) flag = false;
            if (flag) break;
            memset(cnt_s, 0, sizeof(cnt_s));
            memset(cnt_g, 0, sizeof(cnt_g));
            A = B = 0;
            for (int i = 0; i < 10; i++) cnt_s[i] = cnt_s0[i]; // set cnt_s to cnt_s0, start from 0
            for (int i = 0; i < n; i++){
                if (s[i] == g[i]) {
                    A++;
                    cnt_s[s[i]]--;
                }
                else {
                    cnt_g[g[i]]++;
                }
            }
            for (int i = 0; i < 10; i++) { // calculate B, start from 0
                B += min(cnt_s[i], cnt_g[i]);
            }
            cout << "    (" << A << "," << B << ")" << endl;
        }
    }
    return 0;
}