Artifact 3e66f13d80d37e147736bc5c909bff5cbe85a52e:
0000: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0010: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 >.#include <stri
0020: 6e 67 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 ng>.#include <se
0030: 74 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 t>.#include <alg
0040: 6f 72 69 74 68 6d 3e 0a 23 69 6e 63 6c 75 64 65 orithm>.#include
0050: 20 3c 69 74 65 72 61 74 6f 72 3e 0a 75 73 69 6e <iterator>.usin
0060: 67 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b g namespace std;
0070: 0a 0a 73 74 72 75 63 74 20 4d 61 73 74 65 72 62 ..struct Masterb
0080: 72 61 69 6e 0a 7b 0a 09 69 6e 74 20 70 6f 73 73 rain.{..int poss
0090: 69 62 6c 65 53 65 63 72 65 74 73 28 76 65 63 74 ibleSecrets(vect
00a0: 6f 72 3c 73 74 72 69 6e 67 3e 20 67 75 65 73 73 or<string> guess
00b0: 65 73 2c 20 76 65 63 74 6f 72 3c 73 74 72 69 6e es, vector<strin
00c0: 67 3e 20 72 65 73 75 6c 74 73 29 0a 09 7b 0a 09 g> results)..{..
00d0: 09 69 6e 74 20 4e 20 3d 20 67 75 65 73 73 65 73 .int N = guesses
00e0: 2e 73 69 7a 65 28 29 3b 0a 09 09 69 6e 74 20 63 .size();...int c
00f0: 6e 74 20 3d 20 30 3b 0a 09 09 66 6f 72 28 69 6e nt = 0;...for(in
0100: 74 20 6e 3d 30 3b 20 6e 3c 37 2a 37 2a 37 2a 37 t n=0; n<7*7*7*7
0110: 3b 20 2b 2b 6e 29 0a 09 09 7b 0a 09 09 09 69 6e ; ++n)...{....in
0120: 74 20 78 5b 5d 20 3d 20 7b 6e 2f 37 2f 37 2f 37 t x[] = {n/7/7/7
0130: 25 37 2b 31 2c 6e 2f 37 2f 37 25 37 2b 31 2c 6e %7+1,n/7/7%7+1,n
0140: 2f 37 25 37 2b 31 2c 6e 25 37 2b 31 7d 3b 0a 0a /7%7+1,n%7+1};..
0150: 09 09 09 62 6f 6f 6c 20 70 6f 73 73 69 62 6c 65 ...bool possible
0160: 20 3d 20 66 61 6c 73 65 3b 0a 09 09 09 66 6f 72 = false;....for
0170: 28 69 6e 74 20 6c 69 65 3d 30 3b 20 6c 69 65 3c (int lie=0; lie<
0180: 4e 20 26 26 20 21 70 6f 73 73 69 62 6c 65 3b 20 N && !possible;
0190: 2b 2b 6c 69 65 29 0a 09 09 09 7b 0a 09 09 09 09 ++lie)....{.....
01a0: 62 6f 6f 6c 20 70 6f 73 73 69 62 6c 65 5f 62 79 bool possible_by
01b0: 5f 74 68 65 5f 6c 69 65 20 3d 20 74 72 75 65 3b _the_lie = true;
01c0: 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 .....for(int i=0
01d0: 3b 20 69 3c 4e 20 26 26 20 70 6f 73 73 69 62 6c ; i<N && possibl
01e0: 65 5f 62 79 5f 74 68 65 5f 6c 69 65 3b 20 2b 2b e_by_the_lie; ++
01f0: 69 29 0a 09 09 09 09 7b 0a 09 09 09 09 09 69 6e i).....{......in
0200: 74 20 67 5b 5d 20 3d 20 7b 67 75 65 73 73 65 73 t g[] = {guesses
0210: 5b 69 5d 5b 30 5d 2d 27 30 27 2c 67 75 65 73 73 [i][0]-'0',guess
0220: 65 73 5b 69 5d 5b 31 5d 2d 27 30 27 2c 67 75 65 es[i][1]-'0',gue
0230: 73 73 65 73 5b 69 5d 5b 32 5d 2d 27 30 27 2c 67 sses[i][2]-'0',g
0240: 75 65 73 73 65 73 5b 69 5d 5b 33 5d 2d 27 30 27 uesses[i][3]-'0'
0250: 7d 3b 0a 09 09 09 09 09 69 6e 74 20 62 20 3d 20 };......int b =
0260: 72 65 73 75 6c 74 73 5b 69 5d 5b 30 5d 2d 27 30 results[i][0]-'0
0270: 27 3b 0a 09 09 09 09 09 69 6e 74 20 77 20 3d 20 ';......int w =
0280: 72 65 73 75 6c 74 73 5b 69 5d 5b 33 5d 2d 27 30 results[i][3]-'0
0290: 27 3b 0a 0a 09 09 09 09 09 69 66 28 20 28 69 3d ';.......if( (i=
02a0: 3d 6c 69 65 29 20 3d 3d 20 6d 61 74 63 68 28 78 =lie) == match(x
02b0: 2c 67 2c 62 2c 77 29 20 29 0a 09 09 09 09 09 09 ,g,b,w) ).......
02c0: 70 6f 73 73 69 62 6c 65 5f 62 79 5f 74 68 65 5f possible_by_the_
02d0: 6c 69 65 20 3d 20 66 61 6c 73 65 3b 0a 09 09 09 lie = false;....
02e0: 09 7d 0a 09 09 09 09 70 6f 73 73 69 62 6c 65 20 .}.....possible
02f0: 7c 3d 20 70 6f 73 73 69 62 6c 65 5f 62 79 5f 74 |= possible_by_t
0300: 68 65 5f 6c 69 65 3b 0a 09 09 09 7d 0a 09 09 09 he_lie;....}....
0310: 69 66 28 20 70 6f 73 73 69 62 6c 65 20 29 0a 09 if( possible )..
0320: 09 09 09 2b 2b 63 6e 74 3b 0a 09 09 7d 0a 09 09 ...++cnt;...}...
0330: 72 65 74 75 72 6e 20 63 6e 74 3b 0a 09 7d 0a 0a return cnt;..}..
0340: 09 62 6f 6f 6c 20 6d 61 74 63 68 28 69 6e 74 20 .bool match(int
0350: 78 5b 5d 2c 20 69 6e 74 20 67 5b 5d 2c 20 69 6e x[], int g[], in
0360: 74 20 62 2c 20 69 6e 74 20 77 29 0a 09 7b 0a 09 t b, int w)..{..
0370: 09 69 6e 74 20 74 72 75 65 5f 62 20 3d 20 30 3b .int true_b = 0;
0380: 0a 09 09 6d 75 6c 74 69 73 65 74 3c 69 6e 74 3e ...multiset<int>
0390: 20 78 73 2c 20 67 73 3b 0a 09 09 66 6f 72 28 69 xs, gs;...for(i
03a0: 6e 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 nt i=0; i<4; ++i
03b0: 29 0a 09 09 09 69 66 28 20 67 5b 69 5d 20 3d 3d )....if( g[i] ==
03c0: 20 78 5b 69 5d 20 29 0a 09 09 09 09 74 72 75 65 x[i] ).....true
03d0: 5f 62 2b 2b 3b 0a 09 09 09 65 6c 73 65 0a 09 09 _b++;....else...
03e0: 09 09 78 73 2e 69 6e 73 65 72 74 28 78 5b 69 5d ..xs.insert(x[i]
03f0: 29 2c 20 67 73 2e 69 6e 73 65 72 74 28 67 5b 69 ), gs.insert(g[i
0400: 5d 29 3b 0a 09 09 76 65 63 74 6f 72 3c 69 6e 74 ]);...vector<int
0410: 3e 20 70 3b 0a 09 09 73 65 74 5f 69 6e 74 65 72 > p;...set_inter
0420: 73 65 63 74 69 6f 6e 28 78 73 2e 62 65 67 69 6e section(xs.begin
0430: 28 29 2c 20 78 73 2e 65 6e 64 28 29 2c 20 67 73 (), xs.end(), gs
0440: 2e 62 65 67 69 6e 28 29 2c 20 67 73 2e 65 6e 64 .begin(), gs.end
0450: 28 29 2c 20 62 61 63 6b 5f 69 6e 73 65 72 74 65 (), back_inserte
0460: 72 28 70 29 29 3b 0a 09 09 72 65 74 75 72 6e 20 r(p));...return
0470: 74 72 75 65 5f 62 3d 3d 62 20 26 26 20 77 3d 3d true_b==b && w==
0480: 70 2e 73 69 7a 65 28 29 3b 0a 09 7d 0a 7d 3b 0a p.size();..}.};.