Create a gist now

Instantly share code, notes, and snippets.

@arukuka /ICPC2017E.java Secret
Created Jul 14, 2017

What would you like to do?
import java.util.*;
public class Main {
Scanner sc = new Scanner(System.in);
String[] terminal = {
"0",
"1",
"a",
"b",
"c",
"d"
};
String exp;
ArrayList<String> generate(int len) {
// debug(len);
ArrayList<String> list = new ArrayList<>();
if (len > 16) {
return list;
}
// I am E
for (String t : terminal) {
// debug("¥tatom", t);
list.add(t);
}
// -E
ArrayList<String> minus = generate(len + 2);
for (String t : minus) {
if (t.charAt(0) == '-') {
continue;
}
// debug("¥tminus", t);
list.add("-" + t);
}
ArrayList<String> left = generate(len + 5);
ArrayList<String> right = generate(len + 5);
// debug("left & right", left.size(), right.size());
// (E^E)
for (String t : left) {
for (String s : right) {
if (t.charAt(0) == '0') {
continue;
}
if (s.charAt(0) == '0') {
continue;
}
if (s.charAt(0) == t.charAt(0)) {
continue;
}
// if (flag)
// debug("¥t^", t, s);
// StringBuilder sb = new StringBuilder();
// sb.append('(');
// sb.append(t);
// sb.append('^');
// sb.append(s);
// sb.append(')');
list.add("(" + t + "^" + s + ")");
}
}
// debug("left & right 2", left.size(), right.size());
// (E*E)
for (String t : left) {
for (String s : right) {
if (t.charAt(0) == '1') {
continue;
}
if (s.charAt(0) == '1') {
continue;
}
if (s.charAt(0) == t.charAt(0)) {
continue;
}
// debug("¥t*", t, s);
// StringBuilder sb = new StringBuilder();
// sb.append('(');
// sb.append(t);
// sb.append('*');
// sb.append(s);
// sb.append(')');
// list.add(sb.toString());
list.add("(" + t + "*" + s + ")");
}
}
// debug("list size", list.size());
return list;
}
class Node {
int type;
Node left;
Node right;
int index;
int v;
int value(int[] variable) {
// debug(type, left, right, index, v, variable);
if (type < 4) {
return variable[type];
}
if (type == 7) {
return v;
}
if (type == 4) {
int v = left.value(variable);
return 1 - v;
}
int l = left.value(variable);
int r = right.value(variable);
if (type == 5) {
return l ^ r;
}
assert type == 6;
return l * r;
}
}
Node kaiseki(int index) {
// debug(exp, index);
char c = exp.charAt(index);
if (varmap.containsKey(c)) {
Node node = new Node();
node.index = index + 1;
node.type = varmap.get(c);
return node;
}
if (teisuu.contains(c)) {
Node node = new Node();
node.index = index + 1;
node.type = 7;
node.v = c - '0';
return node;
}
if (c == '-') {
Node node = new Node();
Node left = kaiseki(index + 1);
node.left = left;
node.index = left.index;
node.type = 4;
return node;
}
Node node = new Node();
assert c == '(';
Node left = kaiseki(index + 1);
node.left = left;
char d = exp.charAt(left.index);
if (d == '^') {
node.type = 5;
} else {
assert d == '*';
node.type = 6;
}
Node right = kaiseki(left.index + 1);
node.right = right;
assert exp.charAt(right.index) == ')';
node.index = right.index + 1;
return node;
}
HashMap<Character, Integer> varmap = new HashMap<>(10);
HashSet<Character> teisuu = new HashSet<>(10);
void run() {
varmap.put('a', 0);
varmap.put('b', 1);
varmap.put('c', 2);
varmap.put('d', 3);
teisuu.add('0');
teisuu.add('1');
debug("hajimari");
ArrayList<String> list = generate(1);
debug("owari");
for (int turn = 0; ; ++turn) {
debug(turn);
exp = sc.next();
if (exp.charAt(0) == '.') {
break;
}
Node atom = kaiseki(0);
ArrayList<Integer> ans = new ArrayList<>();
for (int a = 0; a < 2; ++a) {
for (int b = 0; b < 2; ++b) {
for (int c = 0; c < 2; ++c) {
for (int d = 0; d < 2; ++d) {
int[] v = new int[]{a, b, c, d};
int w = atom.value(v);
ans.add(w);
}
}
}
}
int min = exp.length();
for (String str : list) {
exp = str;
Node root = kaiseki(0);
ArrayList<Integer> arr = new ArrayList<>();
for (int a = 0; a < 2; ++a) {
for (int b = 0; b < 2; ++b) {
for (int c = 0; c < 2; ++c) {
for (int d = 0; d < 2; ++d) {
int[] v = new int[]{a, b, c, d};
int w = root.value(v);
arr.add(w);
}
}
}
}
if (ans.equals(arr)) {
min = Math.min(min, str.length());
}
}
System.out.println(min);
}
}
int ni() {
return sc.nextInt();
}
public static void main(String[] args) {
new Main().run();
}
void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment