解題區/解題區 - UVa

UVa 1548 - The Game of Master-Mind

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Solution

Problem

擴充版的 1A1B 問題，A 表示猜的數列有多少位置正確，B 表示有多少位置錯，但使用的數字有在正確答案中。現在考慮使用的數字不只有 0 - 9，將會使用 1 - C，同時數列長度為 P，又給定當前的猜測情況，已知數種數列得到的 AB。

找一組滿足所有猜測結果，字典順序最小的那一組答案。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
4 3 2
1 2 3 2
1 1
2 1 3 2
1 1
4 6 2
3 3 3 3
3 0
4 4 4 4
2 0
8 9 3
1 2 3 4 5 6 7 8
0 0
2 3 4 5 6 7 8 9
1 0
3 4 5 6 7 8 9 9
2 0

Output

1
2
3
1 1 1 3
You are cheating!
9 9 9 9 9 9 9 9

Solution

原題使用黑色和白色數量分別表示 AB。

現在考慮回過頭來思考 A B 如何計算。A 就是序列的交集個數，而 B 是集合的交集個數扣除 A 的答案。

這麼一來，窮舉過程中統計序列交集和集合交集會更為方便。依序窮舉每一位的答案，過程中檢查是否存在 A 或 B 超過某一組猜測。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXM = 128;
const int MAXP = 11;
const int MAXC = 128;
int P, C, M;
int B[MAXM], W[MAXM], G[MAXM][MAXP], CG[MAXM][MAXC];
int path[MAXP], bcnt[MAXM], bwcnt[MAXM], CGcnt[MAXC];
// B[i] = |vector_intersection(G, S)|
// W[i] = |set_intersection(G, S)| - B[i]
// ===>|set_intersection(G, S)| = B[i] + W[i]
int checkValid(int p, int c) {
    for (int i = 0; i < M; i++) {
        if (G[i][p] == c && bcnt[i] == B[i])
            return 0; // BLACK exceeded
        if (CGcnt[c] < CG[i][c] && bwcnt[i] == B[i] + W[i])
            return 0; // |set_intersection(G, S)| > B[i] + W[i]
    }
    return 1;
}
void remove(int p, int c) {
    for (int i = 0; i < M; i++) {
        if (G[i][p] == c)
            bcnt[i]++;
        if (CGcnt[c] < CG[i][c])
            bwcnt[i]++;
    }
    CGcnt[c]++;
}
void resume(int p, int c) {
    for (int i = 0; i < M; i++) {
        if (G[i][p] == c)
            bcnt[i]--;
        if (CGcnt[c] <= CG[i][c])
            bwcnt[i]--;
    }
    CGcnt[c]--;
}
int dfs(int idx) {
    if (idx == P) {
        int ok = 1;
        for (int i = 0; i < M && ok; i++)
            ok &= bcnt[i] == B[i] && bwcnt[i] == B[i] + W[i];
        return ok;
    }
    for (int i = 1; i <= C; i++) {
        if (!checkValid(idx, i))
            continue;
        remove(idx, i);
        path[idx] = i;
        if (dfs(idx+1))
            return 1;
        resume(idx, i);
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &P, &C, &M);
        for (int i = 0; i < M; i++) {
            memset(CG[i], 0, sizeof(CG[i]));
            for (int j = 0; j < P; j++) {
                scanf("%d", &G[i][j]);
                CG[i][G[i][j]]++;
            }
            scanf("%d %d", &B[i], &W[i]);
        }
        
        memset(bcnt, 0, sizeof(bcnt));
        memset(bwcnt, 0, sizeof(bwcnt));
        memset(CGcnt, 0, sizeof(CGcnt));
        int f = dfs(0);
        if (f) {
            for (int i = 0; i < P; i++)
                printf("%d%c", path[i], i == P-1 ? '\n' : ' ');
        } else {
            puts("You are cheating!");
        }
    }
    return 0;
}