UVA – 296 – Safe Breaker

Problem Statement : http://acm.uva.es/p/v2/296.html

Type : Mastermind Game

#include <iostream>
#include <set>
#include <stdio.h>

using namespace std;
struct Combination {
int num[4];
int taken[4];
Combination(int N) {
for (size_t i = 0; i < 4; i++)
num[i] = N % 10, N /= 10, taken[i] = 0;
}
int matches(Combination & o) {
int count = 0;
for (size_t i = 0; i < 4; i++) {
if (this->num[i] == o.num[i]) {
count++;
taken[i] = o.taken[i] = 1;
}
}
return count;
}
int contains(Combination & o) {
int count = 0;
for (int i = 0; i < 4; i++) {
if (taken[i])
continue;
for (int j = 0; j < 4; j++) {
if (o.taken[j])
continue;
if (o.num[j] == num[i]) {
count++;
taken[i] = o.taken[j] = 1;
}
}
}
return count;
}
};
struct Guess {
int n, r, w;
Combination com;
Guess() :
r(0), w(0), com(Combination(0)) {
}
;
Guess(int N, int R, int W) :
n(N), r(R), w(W), com(Combination(N)) {
}
bool apply(Combination& c) {
int m = com.matches(c), co = com.contains(c);
return m == r && co == w;
}
void reset() {
com = Combination(n);
}
};
int main(void) {
int T, g, N, R, W;

scanf("%d", &T);
while (T--) {
scanf("%d", &g);
Guess guesses[g];
for (size_t i = 0; i < g; i++) {
scanf("%d %d/%d", &N, &R, &W);
guesses[i] = Guess(N, R, W);
}
int matches = 0;
Combination match(0);
for (int n = 0; n < 10000; n++) {
for (size_t i = 0; i < g; i++) {
guesses[i].reset();
}
bool applyToAll = true;

Combination abc = Combination(n);

if (abc.valid())
for (size_t i = 0; i < g; i++) {
Combination ab = Combination(n);
applyToAll &= guesses[i].apply(ab);
}

if (applyToAll) {
matches++;
match = Combination(n);
}
}
if (!matches)
printf("impossible\n");
else if (matches == 1)
printf("%d%d%d%d\n", match.num[3], match.num[2], match.num[1], match.num[0]);
else if (matches > 1)
printf("indeterminate\n");
}
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: