-
Notifications
You must be signed in to change notification settings - Fork 11
/
SPOJ12.cc
81 lines (73 loc) · 1.66 KB
/
SPOJ12.cc
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
// SPOJ 12: The Game of Master-Mind
// http://www.spoj.com/problems/MMIND/
//
// Solution: exhaustive search
// (Note: Mastermind is NP-hard)
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cmath>
#include <cstring>
#include <functional>
#include <algorithm>
using namespace std;
#define ALL(c) c.begin(), c.end()
#define FOR(i,c) for(typeof(c.begin())i=c.begin();i!=c.end();++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define fst first
#define snd second
int P, C, M;
struct Query {
int guess[105];
int count[105];
int hit, match;
} query[105];
int solution[105];
bool solve(int p) {
REP(m, M)
if (query[m].hit < 0 || query[m].hit > P-p ||
query[m].match < 0 || query[m].match > P-p) return false;
if (p == P) return true;
REP(c, C) {
solution[p] = c;
REP(m, M) {
if (query[m].guess[p] == c) --query[m].hit;
if (query[m].count[c]-- > 0) --query[m].match;
}
if (solve(p+1)) return true;
REP(m, M) {
if (query[m].guess[p] == c) ++query[m].hit;
if (++query[m].count[c] > 0) ++query[m].match;
}
}
return false;
}
void doit() {
memset(query, 0, sizeof(query));
scanf("%d %d %d", &P, &C, &M);
REP(m, M) {
REP(p, P) {
int g; scanf("%d", &g);
query[m].guess[p] = g-1;
++query[m].count[g-1];
}
scanf("%d %d", &query[m].hit, &query[m].match);
query[m].match += query[m].hit;
}
if (solve(0)) {
REP(p, P) {
if (p > 0) printf(" ");
printf("%d", solution[p]+1);
}
printf("\n");
} else {
printf("You are cheating!\n");
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) doit();
}