Skip to content

Instantly share code, notes, and snippets.

@asi1024
Created August 30, 2015 18:12
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save asi1024/b6ccaff88ab81654bce7 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, pi = acos(-1.0);
vector<string> cond;
ll dfs(ll term, int n) {
if (n == (int)cond.size()) return term;
for (char c: cond[n]) {
int t = (c | 32) - 'a';
ll f = (int)(c > 'Z') + 1;
if (((term >> t * 2) & 3) == 3 - f) continue;
if (((term >> t * 2) & 3) == f) return dfs(term, n + 1);
ll res = dfs(term | (f << t * 2), n + 1);
if (res > 0) return res;
term = term | ((3 - f) << t * 2);
}
return 0;
}
int main() {
int N;
while (cin >> N, N) {
cond.clear();
vector<string> str(3);
REP(i,3) cin >> str[i];
REP(i,N) REP(j,8) {
string s;
REP(k,3) s += str[k][i*3+1 + ((j>>k)&1)];
sort(ALL(s));
auto it = unique(ALL(s));
s.resize(it - begin(s));
cond.push_back(s);
}
sort(ALL(cond));
auto it = unique(ALL(cond));
cond.resize(it - begin(cond));
ll term = dfs(0, 0);
if (term != 0) {
vector<string> res;
REP(i,26) if (((term >> i * 2) & 3) == 2) res.push_back(string(1, 'A' + i));
cout << res.size();
for (string s: res) cout << " " << s;
cout << endl;
}
else cout << -1 << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment