uva 296

枚举法

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int t, n, i, j, k;
 7     scanf("%d", &t);
 8     char f[10000][5];
 9     for(i = 0; i <= 9999; i++)
10         sprintf(f[i], "%04d", i);
11 
12     while(t--)
13     {
14         scanf("%d", &n);
15         char G[100][5], A[100], B[100];
16         for(i = 0; i < n; i++)
17             scanf("%s %d/%d", G[i], &A[i], &B[i]);
18 
19         int cnt = 0, ans;
20         char s[5];
21         for(i = 0; i <= 9999; i++)
22         {
23             s[0] = f[i][0];
24             s[1] = f[i][1];
25             s[2] = f[i][2];
26             s[3] = f[i][3];
27             for(j = 0; j < n; j++)
28             {
29                 int num[10] = {}, a = 0, b = 0;
30 
31                 for(k = 0; k < 4; k++)
32                     num[G[j][k] - '0'] ++;
33 
34                 for(k = 0; k < 4; k++)
35                     if(num[s[k]-'0'] > 0)
36                         b++, num[s[k]-'0']--;
37 
38                 for(k = 0; k < 4; k++)
39                     if(s[k] == G[j][k])
40                         a++, b--;
41 
42                 if(A[j] == a && B[j] == b) continue;
43                 else break;
44             }
45             if(j == n)
46             {
47                 cnt ++;
48                 ans = i;
49                 if(cnt == 2)
50                     break;
51             }
52         }
53         if(cnt == 1) printf("%04d
", ans);
54         else if(cnt == 0) puts("impossible");
55         else puts("indeterminate");
56     }
57     return 0;
58 }

 1 #include <iostream>
 2 #include <set>
 3 #include <stdio.h>
 4  
 5 using namespace std;
 6 struct Combination {
 7 int num[4];
 8 int taken[4];
 9 Combination(int N) {
10 for (size_t i = 0; i < 4; i++)
11 num[i] = N % 10, N /= 10, taken[i] = 0;
12 }
13 int matches(Combination & o) {
14 int count = 0;
15 for (size_t i = 0; i < 4; i++) {
16 if (this->num[i] == o.num[i]) {
17 count++;
18 taken[i] = o.taken[i] = 1;
19 }
20 }
21 return count;
22 }
23 int contains(Combination & o) {
24 int count = 0;
25 for (int i = 0; i < 4; i++) {
26 if (taken[i])
27 continue;
28 for (int j = 0; j < 4; j++) {
29 if (o.taken[j])
30 continue;
31 if (o.num[j] == num[i]) {
32 count++;
33 taken[i] = o.taken[j] = 1;
34 }
35 }
36 }
37 return count;
38 }
39 };
40 struct Guess {
41 int n, r, w;
42 Combination com;
43 Guess() :
44 r(0), w(0), com(Combination(0)) {
45 }
46 ;
47 Guess(int N, int R, int W) :
48 n(N), r(R), w(W), com(Combination(N)) {
49 }
50 bool apply(Combination& c) {
51 int m = com.matches(c), co = com.contains(c);
52 return m == r && co == w;
53 }
54 void reset() {
55 com = Combination(n);
56 }
57 };
58 int main(void) {
59 int T, g, N, R, W;
60  
61 scanf("%d", &T);
62 while (T--) {
63 scanf("%d", &g);
64 Guess guesses[g];
65 for (size_t i = 0; i < g; i++) {
66 scanf("%d %d/%d", &N, &R, &W);
67 guesses[i] = Guess(N, R, W);
68 }
69 int matches = 0;
70 Combination match(0);
71 for (int n = 0; n < 10000; n++) {
72 for (size_t i = 0; i < g; i++) {
73 guesses[i].reset();
74 }
75 bool applyToAll = true;
76  
77 Combination abc = Combination(n);
78  
79 if (abc.valid())
80 for (size_t i = 0; i < g; i++) {
81 Combination ab = Combination(n);
82 applyToAll &= guesses[i].apply(ab);
83 }
84  
85 if (applyToAll) {
86 matches++;
87 match = Combination(n);
88 }
89 }
90 if (!matches)
91 printf("impossible
");
92 else if (matches == 1)
93 printf("%d%d%d%d
", match.num[3], match.num[2], match.num[1], match.num[0]);
94 else if (matches > 1)
95 printf("indeterminate
");
96 }
97 return 0;
98 }