ICFPC 2013 最終コード

gistfile1.cpp

#include <unistd.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <iostream>
#include <utility>
#include <string>
#include <random>
#include <memory>

using namespace std;

#define STACK 2

typedef unsigned long long ull;

enum Head {
  ZERO  = 0x100,
  ONE   = 0x110,
  VAR_1 = 0x120,
  VAR_2 = 0x130,
  VAR_3 = 0x140,

  IF0  = 0x103,
  FOLD = 0x213,

  NOT    = 0x111,
  SHL1   = 0x121,
  SHR1   = 0x131,
  SHR4   = 0x141,
  SHR16  = 0x151,

  AND  = 0x112,
  OR   = 0x122,
  XOR  = 0x132,
  PLUS = 0x142,
};

static int nchild(Head h) { return h & 0xF; }
static int hsize(Head h) { return h >> 8; }

struct FNode {
  Head h;
  FNode *next;
};

struct FNode1 : public FNode {
  FNode *t1;
};

struct FNode2 : public FNode {
  FNode *t1;
  FNode *t2;
};

struct FNode3 : public FNode {
  FNode *t1;
  FNode *t2;
  FNode *t3;
};

template<class V>
typename V::ret_t fnode_fold(FNode *tin, typename V::param_t p, V& v)
{
  switch (nchild(tin->h)) {
  case 0: {
    FNode *t = static_cast<FNode *>(tin);
    switch (t->h) {
    case ZERO:
      return v.fold_ZERO(p);
    case ONE:
      return v.fold_ONE(p);
    case VAR_1:
      return v.fold_VAR_1(p);
    case VAR_2:
      return v.fold_VAR_2(p);
    case VAR_3:
      return v.fold_VAR_3(p);
    }
    abort();
  }
  case 1: {
    FNode1 *t = static_cast<FNode1 *>(tin);
    switch (t->h) {
    case NOT:
      return v.fold_NOT(t->t1, p);
    case SHL1:
      return v.fold_SHL1(t->t1, p);
    case SHR1:
      return v.fold_SHR1(t->t1, p);
    case SHR4:
      return v.fold_SHR4(t->t1, p);
    case SHR16:
      return v.fold_SHR16(t->t1, p);
    }
    abort();
  }
  case 2: {
    FNode2 *t = static_cast<FNode2 *>(tin);
    switch (t->h) {
    case AND:
      return v.fold_AND(t->t1, t->t2, p);
    case OR:
      return v.fold_OR(t->t1, t->t2, p);
    case XOR:
      return v.fold_XOR(t->t1, t->t2, p);
    case PLUS:
      return v.fold_PLUS(t->t1, t->t2, p);
    }
    abort();
  }
  case 3: {
    FNode3 *t = static_cast<FNode3 *>(tin);
    switch (t->h) {
    case FOLD:
      return v.fold_FOLD(t->t1, t->t2, t->t3, p);
    case IF0:
      return v.fold_IF0(t->t1, t->t2, t->t3, p);
    }
    abort();
  }
  }
  abort();
}

#if 0

struct Vex
{
  typedef void ret_t;
  typedef int param_t;

  ret_t r(FNode *t, param_t p)
  {
    return fnode_fold(t, p, *this);
  }

  ret_t fold_ZERO(param_t p)
  {
  }

  ret_t fold_ONE(param_t p)
  {
  }

  ret_t fold_VAR_1(param_t p)
  {
  }

  ret_t fold_VAR_2(param_t p)
  {
  }

  ret_t fold_VAR_3(param_t p)
  {
  }

  ret_t fold_NOT(FNode *t1, param_t p)
  {
  }

  ret_t fold_SHL1(FNode *t1, param_t p)
  {
  }

  ret_t fold_SHR1(FNode *t1, param_t p)
  {
  }

  ret_t fold_SHR4(FNode *t1, param_t p)
  {
  }

  ret_t fold_SHR16(FNode *t1, param_t p)
  {
  }

  ret_t fold_AND(FNode *t1, FNode *t2, param_t p)
  {
  }

  ret_t fold_OR(FNode *t1, FNode *t2, param_t p)
  {
  }

  ret_t fold_XOR(FNode *t1, FNode *t2, param_t p)
  {
  }

  ret_t fold_PLUS(FNode *t1, FNode *t2, param_t p)
  {
  }

  ret_t fold_FOLD(FNode *t1, FNode *t2, FNode *t3, param_t p)
  {
  }

  ret_t fold_IF0(FNode *t1, FNode *t2, FNode *t3, param_t p)
  {
  }
};

#endif

struct Vdump
{
  typedef void ret_t;
  typedef ostream& param_t;

  ret_t r(FNode *t, param_t p)
  {
    return fnode_fold(t, p, *this);
  }

  ret_t fold_ZERO(param_t p)
  {
    p << "0";
  }

  ret_t fold_ONE(param_t p)
  {
    p << "1";
  }

  ret_t fold_VAR_1(param_t p)
  {
    p << "x";
  }

  ret_t fold_VAR_2(param_t p)
  {
    p << "y";
  }

  ret_t fold_VAR_3(param_t p)
  {
    p << "z";
  }

  ret_t fold_NOT(FNode *t1, param_t p)
  {
    p << "(not ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_SHL1(FNode *t1, param_t p)
  {
    p << "(shl1 ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_SHR1(FNode *t1, param_t p)
  {
    p << "(shr1 ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_SHR4(FNode *t1, param_t p)
  {
    p << "(shr4 ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_SHR16(FNode *t1, param_t p)
  {
    p << "(shr16 ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_AND(FNode *t1, FNode *t2, param_t p)
  {
    p << "(and ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << ")";
  }

  ret_t fold_OR(FNode *t1, FNode *t2, param_t p)
  {
    p << "(or ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << ")";
  }

  ret_t fold_XOR(FNode *t1, FNode *t2, param_t p)
  {
    p << "(xor ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << ")";
  }

  ret_t fold_PLUS(FNode *t1, FNode *t2, param_t p)
  {
    p << "(plus ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << ")";
  }

  ret_t fold_FOLD(FNode *t1, FNode *t2, FNode *t3, param_t p)
  {
    p << "(fold ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << " (lambda (y z) ";
    r(t3, p);
    p << "))";
  }

  ret_t fold_IF0(FNode *t1, FNode *t2, FNode *t3, param_t p)
  {
    p << "(if0 ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << " ";
    r(t3, p);
    p << ")";    
  }
};

static void fdump(FNode *p, ostream& os)
{
  Vdump().r(p, os);
}

struct Veval
{
  typedef ull ret_t;
  typedef const ull *param_t;

  ret_t r(FNode *t, param_t p)
  {
    return fnode_fold(t, p, *this);
  }

  ret_t fold_ZERO(param_t p)
  {
    return 0;
  }

  ret_t fold_ONE(param_t p)
  {
    return 1;
  }

  ret_t fold_VAR_1(param_t p)
  {
    return p[0];
  }

  ret_t fold_VAR_2(param_t p)
  {
    return p[1];
  }

  ret_t fold_VAR_3(param_t p)
  {
    return p[2];
  }

  ret_t fold_NOT(FNode *t1, param_t p)
  {
    return ~r(t1, p);
  }

  ret_t fold_SHL1(FNode *t1, param_t p)
  {
    return r(t1, p) << 1;
  }

  ret_t fold_SHR1(FNode *t1, param_t p)
  {
    return r(t1, p) >> 1;
  }

  ret_t fold_SHR4(FNode *t1, param_t p)
  {
    return r(t1, p) >> 4;
  }

  ret_t fold_SHR16(FNode *t1, param_t p)
  {
    return r(t1, p) >> 16;
  }

  ret_t fold_AND(FNode *t1, FNode *t2, param_t p)
  {
    return r(t1, p) & r(t2, p);
  }

  ret_t fold_OR(FNode *t1, FNode *t2, param_t p)
  {
    return r(t1, p) | r(t2, p);
  }

  ret_t fold_XOR(FNode *t1, FNode *t2, param_t p)
  {
    return r(t1, p) ^ r(t2, p);
  }

  ret_t fold_PLUS(FNode *t1, FNode *t2, param_t p)
  {
    return r(t1, p) + r(t2, p);
  }

  ret_t fold_FOLD(FNode *t1, FNode *t2, FNode *t3, param_t p)
  {
    ull v1 = r(t1, p);
    ull v2 = r(t2, p);
    ull nv[3];

    nv[0] = p[0];
    nv[2] = v2;

    for (int i = 0; i < 8; i++) {
      nv[1] = v1 & 0xFF;
      nv[2] = r(t3, nv);
      v1 >>= 8;
    }

    return nv[2];
  }

  ret_t fold_IF0(FNode *t1, FNode *t2, FNode *t3, param_t p)
  {
    return r(t1, p) ? r(t3, p) : r(t2, p);
  }
};

static ull feval(FNode *t, ull x)
{
  ull nv[1] = { x };
  return Veval().r(t, nv);
}

struct Vevalc
{
  // (value, is_const)
  typedef pair<ull, bool> ret_t;
  typedef const pair<ull, bool> *param_t;

  ret_t r(FNode *t, param_t p)
  {
    return fnode_fold(t, p, *this);
  }

  ret_t fold_ZERO(param_t p)
  {
    return make_pair(0, true);
  }

  ret_t fold_ONE(param_t p)
  {
    return make_pair(1, true);
  }

  ret_t fold_VAR_1(param_t p)
  {
    return p[0];
  }

  ret_t fold_VAR_2(param_t p)
  {
    return p[1];
  }

  ret_t fold_VAR_3(param_t p)
  {
    return p[2];
  }

  ret_t fold_NOT(FNode *t1, param_t p)
  {
    auto v1 = r(t1, p);
    return make_pair(~v1.first, v1.second);
  }

  ret_t fold_SHL1(FNode *t1, param_t p)
  {
    auto v1 = r(t1, p);
    return make_pair(v1.first << 1, v1.second);
  }

  ret_t fold_SHR1(FNode *t1, param_t p)
  {
    auto v1 = r(t1, p);
    return make_pair(v1.first >> 1, v1.second);
  }

  ret_t fold_SHR4(FNode *t1, param_t p)
  {
    auto v1 = r(t1, p);
    return make_pair(v1.first >> 4, v1.second);
  }

  ret_t fold_SHR16(FNode *t1, param_t p)
  {
    auto v1 = r(t1, p);
    return make_pair(v1.first >> 16, v1.second);
  }

  ret_t fold_AND(FNode *t1, FNode *t2, param_t p)
  {
    auto v1 = r(t1, p);
    if (v1.second) {
      auto v2 = r(t2, p);
      return make_pair(v1.first & v2.first, v1.second && v2.second);
    } else {
      return v1;
    }
  }

  ret_t fold_OR(FNode *t1, FNode *t2, param_t p)
  {
    auto v1 = r(t1, p);
    if (v1.second) {
      auto v2 = r(t2, p);
      return make_pair(v1.first | v2.first, v1.second && v2.second);
    } else {
      return v1;
    }
  }

  ret_t fold_XOR(FNode *t1, FNode *t2, param_t p)
  {
    auto v1 = r(t1, p);
    if (v1.second) {
      auto v2 = r(t2, p);
      return make_pair(v1.first ^ v2.first, v1.second && v2.second);
    } else {
      return v1;
    }
  }

  ret_t fold_PLUS(FNode *t1, FNode *t2, param_t p)
  {
    auto v1 = r(t1, p);
    if (v1.second) {
      auto v2 = r(t2, p);
      return make_pair(v1.first + v2.first, v1.second && v2.second);
    } else {
      return v1;
    }
  }

  ret_t fold_FOLD(FNode *t1, FNode *t2, FNode *t3, param_t p)
  {
    auto v1 = r(t1, p);
    auto v2 = r(t2, p);
    pair<ull, bool> nv[3];

    nv[0] = p[0];
    nv[2] = v2;

    for (int i = 0; i < 8; i++) {
      nv[1] = make_pair(v1.first & 0xFF, v1.second);
      nv[2] = r(t3, nv);
      v1.first >>= 8;
    }

    return nv[2];
  }

  ret_t fold_IF0(FNode *t1, FNode *t2, FNode *t3, param_t p)
  {
    auto v1 = r(t1, p);
    if (v1.second) {
      return v1.first ? r(t3, p) : r(t2, p);
    } else {
      return v1;
    }
  }
};

static pair<ull, bool> fevalc(FNode *t)
{
  pair<ull, bool> nv[3] = { make_pair(0, false), make_pair(0, false), make_pair(0, false) };
  return Vevalc().r(t, nv);
}

template<class FN>
struct Alloc {
  FN *next;

  Alloc() : next(0) {
  }

  FN *alloc()
  {
    if (!next) {
      FN *p = new FN[2048];
      for (int i = 0; i < 2048; i++) {
        p[i].next = next;
        next = &p[i];
      }
    }
    FN *p = next;
    next = static_cast<FN *>(next->next);
    return p;
  }

  FN *free(FN *p)
  {
    p->next = next;
    next = p;
  }
};

static Alloc<FNode1> falloc1;
static Alloc<FNode2> falloc2;
static Alloc<FNode3> falloc3;

//
// fnodes[0][size]: use x
// fnodes[1][size]; use x, y, z
//
static vector<FNode *> fnodes[STACK];

static void addLeafNode(int s, int v, Head h)
{
  FNode *p = new FNode();
  p->h = h;
  p->next = fnodes[v][s];
  fnodes[v][s] = p;
}

static void addFoldNode(int s, int v, FNode *t1, FNode *t2, FNode *t3)
{
  FNode3 *p = falloc3.alloc();
  p->h = FOLD;
  p->t1 = t1;
  p->t2 = t2;
  p->t3 = t3;
  p->next = fnodes[v][s];
  fnodes[v][s] = p;
}

static void addIf0Node(int s, int v, FNode *t1, FNode *t2, FNode *t3)
{
  FNode3 *p = falloc3.alloc();
  p->h = IF0;
  p->t1 = t1;
  p->t2 = t2;
  p->t3 = t3;
  p->next = fnodes[v][s];
  fnodes[v][s] = p;
}

static void addOp2Node(int s, int v, Head h, FNode *t1, FNode *t2)
{
  FNode2 *p = falloc2.alloc();
  p->h = h;
  p->t1 = t1;
  p->t2 = t2;
  p->next = fnodes[v][s];
  fnodes[v][s] = p;
}

static void addOp1Node(int s, int v, Head h, FNode *t1)
{
  FNode1 *p = falloc1.alloc();
  p->h = h;
  p->t1 = t1;
  p->next = fnodes[v][s];
  fnodes[v][s] = p;
}

static FNode *c_zero;
static FNode *c_one;
static FNode *c_var_1;
static FNode *c_var_2;
static FNode *c_var_3;

static pair<int, bool> fhead1(FNode *t)
{
  if (nchild(t->h) == 1) {
    switch (t->h) {
    case NOT:
      return make_pair(0, true);
    case SHL1:
      return make_pair(-1, false);
    case SHR1:
      return make_pair(1, false);
    case SHR4:
      return make_pair(4, false);
    case SHR16:
      return make_pair(16, false);
    }
  } else {
    return make_pair(0, false);
  }
}

static void initFixed(int size)
{
  for (int i = 0; i < STACK; i++) fnodes[i].resize(size + 1, NULL);

  addLeafNode(1, 0, ZERO);
  c_zero = fnodes[0][1];
  addLeafNode(1, 0, ONE);
  c_one = fnodes[0][1];
  addLeafNode(1, 0, VAR_1);
  c_var_1 = fnodes[0][1];
  addLeafNode(1, 1, VAR_2);
  c_var_2 = fnodes[1][1];
  addLeafNode(1, 1, VAR_3);
  c_var_3 = fnodes[1][1];

  for (int s = 2; s <= size; s++) {
    if (s >= 5) {
      for (int s1 = 1; s1 <= s - 4; s1++) {
        for (int s2 = 1; s2 <= s - s1 - 3; s2++) {
          int s3 = s - s1 - s2 - 2;

          for (int v12 = 0; v12 < STACK - 1; v12++) {
            for (int v3 = 0; v3 <= v12 + 1; v3++) {
              for (FNode *t3 = fnodes[v3][s3]; t3; t3 = t3->next) {
                auto c3 = fevalc(t3);
                if (c3.second) continue;

                if (t3 == c_var_3) continue;
              
                for (FNode *t1 = fnodes[v12][s1]; t1; t1 = t1->next) {
                  for (FNode *t2 = fnodes[v12][s2]; t2; t2 = t2->next) {
                    addFoldNode(s, v12, t1, t2, t3);
                  }
                }
              }
            }
          }
        }
      }
    }
    if (s >= 4) {
      for (int s1 = 1; s1 <= s - 3; s1++) {
        for (int s2 = 1; s2 <= s - s1 - 2; s2++) {
          int s3 = s - s1 - s2 - 1;

          for (int v1 = 0; v1 < STACK; v1++) {
            for (int v2 = 0; v2 < STACK; v2++) {
              for (int v3 = 0; v3 < STACK; v3++) {
                int v = max(v1, max(v2, v3));

                for (FNode *t1 = fnodes[v1][s1]; t1; t1 = t1->next) {
                  auto c1 = fevalc(t1);
                  if (c1.second) continue;

                  for (FNode *t2 = fnodes[v2][s2]; t2; t2 = t2->next) {
                    for (FNode *t3 = fnodes[v3][s3]; t3; t3 = t3->next) {
                      addIf0Node(s, v, t1, t2, t3);
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    if (s >= 3) {
      for (int s1 = 1; s1 <= s - 2; s1++) {
        int s2 = s - s1 - 1;
        for (int v1 = 0; v1 < STACK; v1++) {
          for (int v2 = 0; v2 < STACK; v2++) {
            int v = max(v1, v2);
            for (FNode *t1 = fnodes[v1][s1]; t1; t1 = t1->next) {
              auto c1 = fevalc(t1);
              FNode *t2;
              if (v1 == v2 && s1 == s2) {
                t2 = t1->next;
              } else {
                t2 = fnodes[v2][s2];
              }
              for (; t2; t2 = t2->next) {
                bool e_and = true;
                bool e_or = true;
                bool e_xor = true;
                bool e_plus = true;

                if (c1.second) {
                  switch (c1.first) {
                  case 0ULL:
                    continue;
                  case ~0ULL:
                    e_and = e_or = e_xor = false;
                    break;
                  }
                }

                auto c2 = fevalc(t2);

                if (c2.second) {
                  switch (c1.first) {
                  case 0ULL:
                    continue;
                  case ~0ULL:
                    e_and = e_or = e_xor = false;
                    break;
                  }
                }
                if (c1.second && c2.second) {
                  switch (c1.first & c2.first) {
                  case 0ULL: case 1ULL: case ~0ULL: case ~1ULL:
                    e_and = false;
                  }
                  switch (c1.first | c2.first) {
                  case 0ULL: case 1ULL: case ~0ULL: case ~1ULL:
                    e_or = false;
                  }
                  switch (c1.first ^ c2.first) {
                  case 0ULL: case 1ULL: case ~0ULL: case ~1ULL:
                    e_xor = false;
                  }
                  switch (c1.first + c2.first) {
                  case 0ULL: case 1ULL: case ~0ULL: case ~1ULL:
                    e_plus = false;
                  }
                }

                auto h1 = fhead1(t1);
                auto h2 = fhead1(t2);

                if (h1.second && h2.second) {
                  // (op (not ...) (not ...))
                  e_and = e_or = e_xor = false;
                }
                if (h1 == h2) {
                  if (h1.first < 0) {
                    // (op (... << 1) (... << 1))
                    continue;
                  }
                  if (h1.first > 0) {
                    // (op (... >> 1) (... >> 1))
                    e_and = e_or = e_xor = false;
                  }
                }

                if (e_and)  addOp2Node(s, v, AND,  t1, t2);
                if (e_or)   addOp2Node(s, v, OR,   t1, t2);
                if (e_xor)  addOp2Node(s, v, XOR,  t1, t2);
                if (e_plus) addOp2Node(s, v, PLUS, t1, t2);
              }
            }
          }
        }
      }
    }
    {
      int s1 = s - 1;
      for (int v1 = 0; v1 < STACK; v1++) {
        int v = v1;
        for (FNode *t1 = fnodes[v1][s1]; t1; t1 = t1->next) {
          bool e_not = true;
          bool e_shl1 = true;
          bool e_shr1 = true;
          bool e_shr4 = true;
          bool e_shr16 = true;

          auto c1 = fevalc(t1);
          if (c1.second) {
            if (c1.first == 0ULL) {
              e_shl1 = e_shr1 = e_shr4 = e_shr16 = false;
            } else if (c1.first <= 2ULL) {
              e_shr1 = e_shr4 = e_shr16 = false;
            } else if (c1.first <= 0x10uLL) {
              e_shr4 = e_shr16 = false;
            } else if (c1.first <= 0x10000) {
              e_shr16 = false;
            }
            switch (~c1.first) {
            case 0ULL: case 1ULL: e_not = false;
            }
          }

          if (nchild(t1->h) == 1) {
            switch (t1->h) {
            case SHR1:
              e_shr4 = e_shr16 = false;
              break;
            case SHR4:
              e_shr16 = false;
              break;
            }
          }

          if (e_not)   addOp1Node(s, v, NOT,   t1);
          if (e_shl1)  addOp1Node(s, v, SHL1,  t1);
          if (e_shr1)  addOp1Node(s, v, SHR1,  t1);
          if (e_shr4)  addOp1Node(s, v, SHR4,  t1);
          if (e_shr16) addOp1Node(s, v, SHR16, t1);
        }
      }
    }
  }
}

static vector<pair<ull, ull> > evalResults;

static void doEval(const vector<ull>& v)
{
  for (auto i = v.begin(); i != v.end();) {
    cout << 'E';
    int n = 0;
    for (auto j = i; j != v.end() && n < 256; j++, n++) {
      if (j != i) cout << " ";
      cout << *j;
    }
    cout << endl;

    auto j = i;
    for (int k = 0; k < n; k++, j++) {
      ull v;
      cin >> v;
      evalResults.push_back(make_pair(*j, v));
    }
    cin.ignore(256, '\n');
    i = i + n;
  }
}

static int doGuess(FNode *p)
{
  cout << 'G';
  cout << "(lambda (x) ";
  fdump(p, cout);
  cout << ")";
  cout << endl;

  int c = cin.get();
  if (c == 'W') {
    cin.ignore(256, '\n');
    return 1;
  } else if (c == 'M') {
    ull x, y, z;
    cin >> x >> y >> z;
    evalResults.push_back(make_pair(x, y));
    cin.ignore(256, '\n');
  }
  return 0;
}

struct DyNode;
typedef shared_ptr<DyNode> PyNode;

struct DyNode {
  Head h;
  PyNode cs[3];
  FNode *t;

  DyNode(Head h) : h(h), t(0)
  {
  }

  DyNode(FNode *p) : h(p->h), t(p)
  {
  }
};

static PyNode start_modify(FNode *t)
{
  PyNode p(new DyNode(t->h));

  switch (nchild(t->h)) {
  case 0:
    break;
  case 1: {
    FNode1 *x = static_cast<FNode1 *>(t);
    p->cs[0] = start_modify(x->t1);
    break;
  }
  case 2: {
    FNode2 *x = static_cast<FNode2 *>(t);
    p->cs[0] = start_modify(x->t1);
    p->cs[1] = start_modify(x->t2);
    break;
  }
  case 3: {
    FNode3 *x = static_cast<FNode3 *>(t);
    p->cs[0] = start_modify(x->t1);
    p->cs[1] = start_modify(x->t2);
    p->cs[2] = start_modify(x->t3);
    break;
  }
  }
  p->t = 0;
  return p;
}

static PyNode pdup(PyNode t)
{
  if (t->t) {
    return start_modify(t->t);
  } else {
    PyNode p(new DyNode(t->h));

    for (int i = 0; i < nchild(p->h); i++) {
      p->cs[i] = pdup(t->cs[i]);
    }
    p->t = 0;

    return p;
  }
}

template<class V>
typename V::ret_t pnode_fold(PyNode t, typename V::param_t p, V& v)
{
  if (t->t) {
    return v.fold_Fixed(t->t, p);
  }
  switch (nchild(t->h)) {
  case 0: {
    switch (t->h) {
    case ZERO:
      return v.fold_ZERO(p);
    case ONE:
      return v.fold_ONE(p);
    case VAR_1:
      return v.fold_VAR_1(p);
    case VAR_2:
      return v.fold_VAR_2(p);
    case VAR_3:
      return v.fold_VAR_3(p);
    }
    abort();
  }
  case 1: {
    switch (t->h) {
    case NOT:
      return v.fold_NOT(t->cs[0], p);
    case SHL1:
      return v.fold_SHL1(t->cs[0], p);
    case SHR1:
      return v.fold_SHR1(t->cs[0], p);
    case SHR4:
      return v.fold_SHR4(t->cs[0], p);
    case SHR16:
      return v.fold_SHR16(t->cs[0], p);
    }
    abort();
  }
  case 2: {
    switch (t->h) {
    case AND:
      return v.fold_AND(t->cs[0], t->cs[1], p);
    case OR:
      return v.fold_OR(t->cs[0], t->cs[1], p);
    case XOR:
      return v.fold_XOR(t->cs[0], t->cs[1], p);
    case PLUS:
      return v.fold_PLUS(t->cs[0], t->cs[1], p);
    }
    abort();
  }
  case 3: {
    switch (t->h) {
    case FOLD:
      return v.fold_FOLD(t->cs[0], t->cs[1], t->cs[2], p);
    case IF0:
      return v.fold_IF0(t->cs[0], t->cs[1], t->cs[2], p);
    }
    abort();
  }
  }
  abort();
}

struct VPdump
{
  typedef void ret_t;
  typedef ostream& param_t;

  ret_t r(PyNode t, param_t p)
  {
    return pnode_fold(t, p, *this);
  }

  ret_t fold_Fixed(FNode *t1, param_t p)
  {
    fdump(t1, p);
  }

  ret_t fold_ZERO(param_t p)
  {
    p << "0";
  }

  ret_t fold_ONE(param_t p)
  {
    p << "1";
  }

  ret_t fold_VAR_1(param_t p)
  {
    p << "x";
  }

  ret_t fold_VAR_2(param_t p)
  {
    p << "y";
  }

  ret_t fold_VAR_3(param_t p)
  {
    p << "z";
  }

  ret_t fold_NOT(PyNode t1, param_t p)
  {
    p << "(not ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_SHL1(PyNode t1, param_t p)
  {
    p << "(shl1 ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_SHR1(PyNode t1, param_t p)
  {
    p << "(shr1 ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_SHR4(PyNode t1, param_t p)
  {
    p << "(shr4 ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_SHR16(PyNode t1, param_t p)
  {
    p << "(shr16 ";
    r(t1, p);
    p << ")";
  }

  ret_t fold_AND(PyNode t1, PyNode t2, param_t p)
  {
    p << "(and ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << ")";
  }

  ret_t fold_OR(PyNode t1, PyNode t2, param_t p)
  {
    p << "(or ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << ")";
  }

  ret_t fold_XOR(PyNode t1, PyNode t2, param_t p)
  {
    p << "(xor ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << ")";
  }

  ret_t fold_PLUS(PyNode t1, PyNode t2, param_t p)
  {
    p << "(plus ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << ")";
  }

  ret_t fold_FOLD(PyNode t1, PyNode t2, PyNode t3, param_t p)
  {
    p << "(fold ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << " (lambda (y z) ";
    r(t3, p);
    p << "))";
  }

  ret_t fold_IF0(PyNode t1, PyNode t2, PyNode t3, param_t p)
  {
    p << "(if0 ";
    r(t1, p);
    p << " ";
    r(t2, p);
    p << " ";
    r(t3, p);
    p << ")";    
  }
};

static void pdump(PyNode t1, ostream& os)
{
  VPdump().r(t1, os);
}

static int doPGuess(PyNode p, bool tfold)
{
  cout << 'G';
  if (tfold) {
    cout << "(lambda (x) (fold x 0 (lambda (y z) ";
    pdump(p, cout);
    cout << ")))";
  } else {
    cout << "(lambda (x) ";
    pdump(p, cout);
    cout << ")";
  }
  cout << endl;

  int c = cin.get();
  if (c == 'W') {
    cin.ignore(256, '\n');
    return 1;
  } else if (c == 'M') {
    ull x, y, z;
    cin >> x >> y >> z;
    evalResults.push_back(make_pair(x, y));
    cin.ignore(256, '\n');
  }
  return 0;
}

static int doBGuess(FNode *ifp, FNode *thp, FNode *elp)
{
  cout << 'G';
  cout << "(lambda (x) (if0 ";
  fdump(ifp, cout);
  cout << " ";
  fdump(thp, cout);
  cout << " ";
  fdump(elp, cout);
  cout << "))";

  cout << endl;

  int c = cin.get();
  if (c == 'W') {
    cin.ignore(256, '\n');
    return 1;
  } else if (c == 'M') {
    ull x, y, z;
    cin >> x >> y >> z;
    evalResults.push_back(make_pair(x, y));
    cin.ignore(256, '\n');
  }
  return 0;
}

static void dumpConst(ull v, ostream& os)
{
  // (or 1 (shl1 (shl1 (or 1 ...))))
  for (int i = 0; i < 64; i++) {
    if (v & (1ULL << i)) {
      os << "(or 1 (shl1 ";
    } else {
      os << "(shl1 ";
    }
  }
  cout << "0";
  for (int i = 0; i < 64; i++) {
    if (v & (1ULL << i)) {
      os << "))";
    } else {
      os << ")";
    }
  }
}

static int doBGuess1(const vector<pair<ull, ull> >& ex, FNode *thp, FNode *elp)
{
  cout << 'G';
  cout << "(lambda (x) (if0 ";
  //// if (if (x ^ ex[0]) 0 (if (x ^ ex[1]) 0 (if ... 0 1))) thp elp 
  for (auto i = ex.begin(); i != ex.end(); ++i) {
    cout << "(if0 (xor x ";
    dumpConst(i->first, cout);
    cout << ") 0 ";
  }
  cout << "1";
  for (auto i = ex.begin(); i != ex.end(); ++i) {
    cout << ")";
  }
  cout << " ";
  fdump(thp, cout);
  cout << " ";
  fdump(elp, cout);
  cout << "))";

  cout << endl;

  int c = cin.get();
  if (c == 'W') {
    cin.ignore(256, '\n');
    return 1;
  } else if (c == 'M') {
    ull x, y, z;
    cin >> x >> y >> z;
    evalResults.push_back(make_pair(x, y));
    cin.ignore(256, '\n');
  }
  return 0;
}


struct VPeval
{
  typedef ull ret_t;
  typedef const ull *param_t;

  ret_t r(PyNode t, param_t p)
  {
    return pnode_fold(t, p, *this);
  }

  ret_t fold_Fixed(FNode *t, param_t p)
  {
    return Veval().r(t, p);
  }

  ret_t fold_ZERO(param_t p)
  {
    return 0;
  }

  ret_t fold_ONE(param_t p)
  {
    return 1;
  }

  ret_t fold_VAR_1(param_t p)
  {
    return p[0];
  }

  ret_t fold_VAR_2(param_t p)
  {
    return p[1];
  }

  ret_t fold_VAR_3(param_t p)
  {
    return p[2];
  }

  ret_t fold_NOT(PyNode t1, param_t p)
  {
    return ~r(t1, p);
  }

  ret_t fold_SHL1(PyNode t1, param_t p)
  {
    return r(t1, p) << 1;
  }

  ret_t fold_SHR1(PyNode t1, param_t p)
  {
    return r(t1, p) >> 1;
  }

  ret_t fold_SHR4(PyNode t1, param_t p)
  {
    return r(t1, p) >> 4;
  }

  ret_t fold_SHR16(PyNode t1, param_t p)
  {
    return r(t1, p) >> 16;
  }

  ret_t fold_AND(PyNode t1, PyNode t2, param_t p)
  {
    return r(t1, p) & r(t2, p);
  }

  ret_t fold_OR(PyNode t1, PyNode t2, param_t p)
  {
    return r(t1, p) | r(t2, p);
  }

  ret_t fold_XOR(PyNode t1, PyNode t2, param_t p)
  {
    return r(t1, p) ^ r(t2, p);
  }

  ret_t fold_PLUS(PyNode t1, PyNode t2, param_t p)
  {
    return r(t1, p) + r(t2, p);
  }

  ret_t fold_FOLD(PyNode t1, PyNode t2, PyNode t3, param_t p)
  {
    ull v1 = r(t1, p);
    ull v2 = r(t2, p);
    ull nv[3];

    nv[0] = p[0];
    nv[2] = v2;

    for (int i = 0; i < 8; i++) {
      nv[1] = v1 & 0xFF;
      nv[2] = r(t3, nv);
      v1 >>= 8;
    }

    return nv[2];
  }

  ret_t fold_IF0(PyNode t1, PyNode t2, PyNode t3, param_t p)
  {
    return r(t1, p) ? r(t3, p) : r(t2, p);
  }
};

static ull peval(PyNode t1, ull v, bool tfold)
{
  ull nv[3] = { v, 0, 0 };

  if (tfold) {
    ull v1 = v;
    nv[2] = 0;

    for (int i = 0; i < 8; i++) {
      nv[1] = v1 & 0xFF;
      nv[2] = VPeval().r(t1, nv);
      v1 >>= 8;
    }

    return nv[2];
  } else {
    VPeval().r(t1, nv);
  }
}

static size_t psize(PyNode t1)
{
  size_t n;

  n += hsize(t1->h);
  for (int i = 0; i < 3; i++) {
    if (t1->cs[i]) {
      n += psize(t1->cs[i]);
    }
  }

  return n;
}

struct Solver
{
  bool isBonus;
  bool isTFold;
  bool enableFold, enableIf0;
  bool enableNot, enableShl1, enableShr1, enableShr4, enableShr16;
  bool enableAnd, enableOr, enableXor, enablePlus;

  Solver()
  {
    isBonus = false;
    isTFold = false;
    enableFold = false;
    enableIf0 = false;
    enableNot = false;
    enableShl1 = false;
    enableShr1 = false;
    enableShr4 = false;
    enableShr16 = false;
    enableAnd = false;
    enableOr = false;
    enableXor = false;
    enablePlus = false;
  }

  mt19937_64 mt;

  void initialEval()
  {
    vector<ull> v;

    v.push_back(0x0123456789ABCDEFull);
    v.push_back(0xFEDCBA9876543210ull);

    for (int i = 0; i < 32; i++) {
      if (isBonus) {
        v.push_back(mt() & 0x000000FFFF000000uLL);
      } else {
        v.push_back(mt());
      }
    }

    for (int i = 0; i < 64; i++) {
      v.push_back(1ULL << i);
    }

    doEval(v);
  }

  bool ev(FNode *p, const pair<ull, ull>& v)
  {
    if (feval(p, v.first) != v.second) {
      return false;
    }
    return true;
  }

  int norm(ull v)
  {
    return __builtin_popcountll(v);
  }

  ull evptop(PyNode p, ull v)
  {
    return peval(p, v, isTFold);
  }

  int evnorm(FNode *p, const pair<ull, ull>& v)
  {
    return norm(feval(p, v.first) ^ v.second);
  }

  int evpnorm(PyNode p, const pair<ull, ull>& v)
  {
    return norm(evptop(p, v.first) ^ v.second);
  }

  template<class I>
  bool ev(FNode *p, I begin, I end)
  {
    for (auto i = begin; i != end; ++i) {
      if (!ev(p, *i)) return false;
    }
    return true;
  } 

  template<class I>
  bool evTfold(FNode *p, I begin, I end)
  {
    FNode3 tf;
    tf.h = FOLD;
    tf.next = NULL;
    tf.t1 = c_var_1;
    tf.t2 = c_zero;
    tf.t3 = p;
    return ev(&tf, begin, end);
  }

  template<class I>
  double evnorm(FNode *p, I begin, I end)
  {
    int v = 0;

    if (begin == end) return 0;

    for (auto i = begin; i != end; ++i) {
      int n = evnorm(p, *i);

      v += n;
    }

    return v / (double)(end - begin);
  }

  template<class I>
  double evpnorm(PyNode p, I begin, I end)
  {
    int v = 0;

    if (begin == end) return 0;

    for (auto i = begin; i != end; ++i) {
      int n = evpnorm(p, *i);

      v += n;
    }

    return v / (double)(end - begin);
  }

  bool solveSmall(bool fstonly)
  {
    vector<FNode *> candidates;

    if (isTFold) {
      for (int v = 0; v < STACK; v++) {
        for (auto i = fnodes[v].begin(); i != fnodes[v].end(); ++i) {
          for (auto p = *i; p; p = p->next) {
            if (evTfold(p, evalResults.begin(), evalResults.end())) {
              candidates.push_back(p);
              if (fstonly) goto found;
            }
          }
        }
      }
    } else {
      for (auto i = fnodes[0].begin(); i != fnodes[0].end(); ++i) {
        for (auto p = *i; p; p = p->next) {
          if (ev(p, evalResults.begin(), evalResults.end())) {
            candidates.push_back(p);
            if (fstonly) goto found;
          }
        }
      }
    }
  found:
    
    size_t checked = evalResults.size();
    while (candidates.size() > 0) {
      cerr << candidates.size() << " entries" << endl;

      if (isTFold) {
        FNode3 tf;
        tf.h = FOLD;
        tf.next = NULL;
        tf.t1 = c_var_1;
        tf.t2 = c_zero;
        tf.t3 = candidates[0];
        if (doGuess(&tf)) {
          return true;
        }
      } else {
        if (doGuess(candidates[0])) {
          return true;
        }
      }

      vector<FNode *> newC;
      for (auto ci = candidates.begin(); ci != candidates.end(); ++ci) {
        if (isTFold) {
          if (evTfold(*ci, evalResults.begin() + checked, evalResults.end())) {
            newC.push_back(*ci);
          }
        } else {
          if (ev(*ci, evalResults.begin() + checked, evalResults.end())) {
            newC.push_back(*ci);
          }
        }
      }
      candidates.swap(newC);
      checked = evalResults.size();

    }
    return false;
  }

  template<class I>
  FNode *findBest(I begin, I end)
  {
    FNode *best = 0;
    double m = 0;

    for (auto i = fnodes[0].begin(); i != fnodes[0].end(); ++i) {
      for (auto p = *i; p; p = p->next) {
        double x = evnorm(p, begin, end);
        if (!best || m > x) {
          best = p;
          m = x;
        }
      }
    }
    cerr << m << endl;
    return best;
  }

  PyNode best_reform;
  double best_reform_score;
  PyNode reform_top;

  void eval_reform()
  {
    double x = evpnorm(reform_top, evalResults.begin(), evalResults.end());

    //cerr << "reform: ";
    //pdump(reform_top, cerr);
    //cerr << endl;

    if (!best_reform || best_reform_score > x) {
      best_reform = pdup(reform_top);
      best_reform_score = x;
    }
  }

  void reform_rec(PyNode cur, int v)
  {
    size_t size = psize(cur);

    for (int v1 = 0; v1 <= v; v1++) {
      if (!(size + 1 < fnodes[v1].size())) continue;

      for (auto i = fnodes[v1].begin() + size + 1; i != fnodes[v1].end(); ++i) {
        for (auto p = *i; p; p = p->next) {
          cur->t = p;
          eval_reform();
          cur->t = NULL;
        }
      }
    }
    if (cur->h == FOLD) {
      reform_rec(cur->cs[0], v);
      reform_rec(cur->cs[1], v);
      if (v == 0) {
        reform_rec(cur->cs[0], 1);
      }
    } else {
      for (int i = 0; i < nchild(cur->h); i++) {
        reform_rec(cur->cs[i], v);
      }
    }
  }

  PyNode reform(PyNode p)
  {
    cerr << "reforming: ";
    pdump(p, cerr);
    cerr << endl;

    best_reform.reset();
    best_reform_score = 0;

    reform_top = p;

    for (int i = 0; i < 3; i++) {
      if (p->cs[i])
        reform_rec(p->cs[i], isTFold ? 1 : 0);
    }

    cerr << "reformed: " << best_reform_score << endl;
    pdump(best_reform, cerr);
    cerr << endl;

    return best_reform;
  }

  bool solveLarge()
  {
    FNode *init_best = findBest(evalResults.begin(), evalResults.begin() + 32);

    cerr << "best match: ";
    fdump(init_best, cerr);
    cerr << endl;

    PyNode templ = start_modify(init_best);
    for (int c = 0; c < 5; c++) {
      templ = reform(templ);
      
      if (doPGuess(templ, isTFold)) {
        return true;
      }

    }

    return false;
  }

  void moreData()
  {
    vector<ull> v;

    for (int i = 0; i < 32; i++) {
      v.push_back(mt());
    }

    doEval(v);
  }

  bool solveBonus()
  {
    for (int cnt = 0; cnt < 10; cnt++) {
      FNode *fst_term = findBest(evalResults.begin(), evalResults.end());
      
      vector<pair<ull, ull> > mustFst;
      vector<pair<ull, ull> > notFst;


      for (auto i = evalResults.begin(); i != evalResults.end(); ++i) {
        if (ev(fst_term, *i)) {
          //fstResult.push_back(*i);
        } else {
          notFst.push_back(*i);
        }
      }

      for (int cnt2 = 0; cnt2 < 4; cnt2++) {

        vector<FNode *> candidates;

        for (auto i = fnodes[0].begin(); i != fnodes[0].end(); ++i) {
          for (auto p = *i; p; p = p->next) {
            if (ev(p, notFst.begin(), notFst.end()))
              candidates.push_back(p);
          }
        }

        if (candidates.size() == 0) {
          moreData();
          goto search_fst;
        }
        cerr << "cand: " << candidates.size() << endl;

        for (auto sndp = candidates.begin(); sndp != candidates.end(); ++sndp) {
          cerr << "search "  << endl;
          FNode *snd_term = *sndp;
          FNode *if_term = NULL;
          bool reverse = false;

          for (auto i = fnodes[0].begin(); i != fnodes[0].end(); ++i) {
            for (auto p = *i; p; p = p->next) {
              for (auto k = mustFst.begin(); k != mustFst.end(); ++k) {
                if (feval(p, k->first) != 0) goto fail;
              }
              for (auto k = notFst.begin(); k != notFst.end(); ++k) {
                if (feval(p, k->first) == 0) goto fail;
              }
              for (auto k = evalResults.begin(); k != evalResults.end(); k++) {
                if (feval(p, k->first)) {
                  if (!ev(snd_term, *k)) goto fail;
                } else {
                  if (!ev(fst_term, *k)) goto fail;
                }
              }
              if_term = p;
              goto ok;
            fail:
              for (auto k = mustFst.begin(); k != mustFst.end(); ++k) {
                if (feval(p, k->first) == 0) goto fail2;
              }
              for (auto k = notFst.begin(); k != notFst.end(); ++k) {
                if (feval(p, k->first) != 0) goto fail2;
              }
              for (auto k = evalResults.begin(); k != evalResults.end(); k++) {
                if (feval(p, k->first)) {
                  if (!ev(fst_term, *k)) goto fail2;
                } else {
                  if (!ev(snd_term, *k)) goto fail2;
                }
              }
              if_term = p;
              reverse = true;
              goto ok;
            fail2:;
            }
          }
        ok:
          if (if_term) {
            if (reverse) {
              if (doBGuess(if_term, fst_term, snd_term)) return true;
            } else {
              if (doBGuess(if_term, snd_term, fst_term)) return true;
            }
            auto miss = evalResults.back();

            bool f = feval(if_term, miss.first) == 0;
            if (reverse) f = !f;

            if (f) {
              // snd_term
              if (ev(fst_term, miss)) {
                // f has problem
                cerr << "bad f" << endl;
                mustFst.push_back(miss);
              } else {
                // snd hint
                cerr << "snd update" << endl;
              }
            } else {
              // fst_term
              cerr << "not fst" << endl;
              notFst.push_back(miss);
              break;
            }
          }
          break;
        }
      }
    search_fst:;
    }
    return false;
  }

  void run()
  {
    initialEval();
    if (isBonus && solveBonus()) {
      return;
    }
    if (solveSmall(true)) {
      return;
    }
    if (solveSmall(false)) {
      return;
    }
    //solveLarge();
  }
};

int main(int argc, char **argv)
{
  alarm(4 * 60);
  Solver sv;

  int size = atoi(argv[2]);
  cerr << "size: " << size << endl;

  for (int i = 3; i < argc; i++) {
    string s = argv[i];

    cerr << "enable: " << s << endl;
    if (s == "bonus") {
      sv.isBonus = true;
    } else if (s == "tfold") {
      sv.isTFold = true;
    } else if (s == "fold") {
      sv.enableFold = true;
    } else if (s == "if0") {
      sv.enableIf0 = true;
    } else if (s == "not") {
      sv.enableNot = true;
    } else if (s == "shl1") {
      sv.enableShl1 = true;
    } else if (s == "shr1") {
      sv.enableShr1 = true;
    } else if (s == "shr4") {
      sv.enableShr4 = true;
    } else if (s == "shr16") {
      sv.enableShr16 = true;
    } else if (s == "and") {
      sv.enableAnd = true;
    } else if (s == "or") {
      sv.enableOr = true;
    } else if (s == "xor") {
      sv.enableXor = true;
    } else if (s == "plus") {
      sv.enablePlus = true;
    } else {
      cerr << "unknown option" << endl;
      exit(1);
    }
  }

  cerr << "initialize constant terms..." << endl;
  if (sv.isBonus) {
    initFixed(7);
  } else {
    initFixed(9);
  }
  cerr << "done" << endl;

  sv.run();
  //fdump(fnodes[0][8], cout);
  //cout << endl;

  return 0;
}