2015
07-16

# Logical Expression

Happy birthday to you!

Just as expected, he smirks, and then says slowly: "This device is my new invention. Only you, my most brilliant student, deserve to have it."

"Thanks, I will keep it up." You reply.

"However," silent for a while, he starts again: "unfortunately, I have lost its original circuit diagram. So I need you to do some researches on it and use a simple logical expression to describe its characteristics. You won’t let me down, will you?"

He laughs, pats you on the back, then turns and stalks off, leaves you, the poor guy, with the "gift" on your hands.

You collect yourself, and start looking at the "lovely" thing. It is a black box, with n inputs labeled from the first capital letter (A) to the n-th capital letter, as well as one unique output. All the inputs and the output are one-bit binary numbers (either 0 or 1).

Then you sit down, put the device on the desk, take out the tools, examine all possible combinations of input values and record the output on the paper.

After everything gets ready, now it is just a piece of cake for you to give a correct logical expression for it.

A correct logical expression should be:
1. A not null string only contains ‘+’, ‘-’ and capital letters from the first (A) to the n-th;
2. A single capital letter in range is a legal logical expression, and its output equals to the value of the input labeled by this letter;
3. If E is a legal logical expression, then NOT operation -E is a legal logical expression;
4. If E and F are legal logical expressions, then AND operation EF is a legal logical expression;
5. If E and F are legal logical expressions, then OR operation E+F is a legal logical expression;
6. In a legal logical expression, you should first do NOT operations from the left to the right, then AND operations from the left to the right, and finally the OR operations from the left to the right;
7. A logical expression is correct if and only if with any possible combinations of input values, its output is the same as which the device outputs.

But as a down-to-earth idealist, you are never satisfied with this. You want to give the most beautiful logical expression like this:
1. It is a correct logical expression;
2. It is the shortest one (not null) among all correct logical expressions;
3. If there are still many available logical expressions, choose the lexicographically least one.

There are several test cases in the input.

Each test case begins with one integer n (1 <= n <= 5), indicating the number of inputs of the device.
Then 2n lines follow. Each line contains (n + 1) one-bit binary numbers, separated by spaces. The first n numbers indicate the value of the n inputs in order, and the last one is the corresponding output.
The 2n sets of inputs are different with each other.
The input ends with n = 0.

There are several test cases in the input.

Each test case begins with one integer n (1 <= n <= 5), indicating the number of inputs of the device.
Then 2n lines follow. Each line contains (n + 1) one-bit binary numbers, separated by spaces. The first n numbers indicate the value of the n inputs in order, and the last one is the corresponding output.
The 2n sets of inputs are different with each other.
The input ends with n = 0.

3
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
0

-A-CB+-BC+AC
Hint
In ASCII table, '+' < '-' < 'A' < 'B' < 'C' < 'D' < 'E'.


## Abstract

HDU 4413 Logical Expression

## Body

### Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

typedef pair<string, int> node;
vector<node> ans;
bool vis[50];
int V[50];

bool cmp(string s1,string s2){
return s1+s2<s2+s1;
}
bool cmp2(string s1,string s2){
return s1+"+"+s2<s2+"+"+s1;
}
bool hmr(node a, node b) {
if (a.second==b.second) {
if (a.first.length()==b.first.length()) return a.first<b.first;
return a.first.length()<b.first.length();
}
return a.second<b.second;
}

bool operator==(node a, node b) {
return a.first==b.first && a.second==b.second;
}

string StInS(int s,int n,int ors){
int i;
vector<string> tmpAns;
for (i=0;i<(1<<n);i++){
if ((i&s)==(ors&s))
if (V[i]==0) return "";
}
if (s==0) return "1";
string tmp;
for (i=0;i<n;i++) if (s&(1<<i)){
tmp="";
if (!(ors&(1<<i)))
tmp+='-';
tmp+=(char)(i+'A');
tmpAns.push_back(tmp);
}
sort(tmpAns.begin(),tmpAns.end(),cmp);
tmp="";
for (i=0;i<tmpAns.size();i++)
tmp+=tmpAns[i];
return tmp;
}

void getans(int s, int n) {
int i,j;
int minsize = 0x3fff;
vector<node> tmp;
for (i=0;i<(1<<n);i++) {
int ctrl=__builtin_popcount(i);
if (ctrl>minsize) continue;
string tans2=StInS(i,n,s);
if (tans2.empty()) continue;
if (ctrl<minsize) {
minsize = ctrl;
tmp.clear();
}
int res = 0;
for (j = 0; j < 1<<n; ++j)
if ((j&i)==(s&i)) res |= 1<<j;
tmp.push_back(make_pair(tans2, res));
}
for (i = 0; i < tmp.size(); ++i)
ans.push_back(tmp[i]);
}

int N, M;
int all;
int best;
bool use[64], ause[64];

void dfs(int i, int len, int cover) {
if (len >= best) return;
if (cover==all) {
memcpy(ause, use, sizeof(use));
best = len;
return;
}
if (i==M) return;
use[i] = 1;
dfs(i+1, len+ans[i].first.length()+1, cover|ans[i].second);
use[i] = 0;
dfs(i+1, len, cover);
}

int main(){
int i,s,j,v;
int cas=0;
for (;;){
scanf("%d",&N);
if (N==0) break;
for (i=0;i<(1<<N);i++){
s=0;
vis[i] = 0;
for (j=0;j<N;j++){
scanf("%d",&v);
s^=(v<<j);
}
scanf("%d",&V[s]);
}
ans.clear();
memset(vis, 0, sizeof vis);
all = 0;
for (s = 0; s < 1<<N; ++s)
if (V[s]){
all |= 1<<s;
getans(s, N);
}
if (ans.size()==0) {
puts("-AA");
continue;
}
if (ans[0].first[0]=='1') {
puts("-A+A");
continue;
}
sort(ans.begin(), ans.end(), hmr);
M = unique(ans.begin(), ans.end())-ans.begin();
sort(ans.begin(), ans.begin()+M);
best = 0x3fffffff;
memset(use, 0, sizeof use);
memset(ause, 0, sizeof ause);
dfs(0, 0, 0);
vector<string> astr;
for (i = 0; i < M; ++i)
if (ause[i]) astr.push_back(ans[i].first);
sort(astr.begin(), astr.end(), cmp2);
string fin = astr[0];
for (i = 1; i < astr.size(); ++i)
fin += "+"+astr[i];
cout << fin << '\n';
}
return 0;
}