Uva 10051

gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

struct Pair {
  int idx;
  int face;
  Pair() : idx(-1), face(-1) {}
  Pair(int idx, int face) : idx(idx), face(face) {}
};

struct Cube {
  int colors[6];
  Pair preds[6];
};

struct Item {
  Pair p;
  int height;
  Item() : p(), height(0) {}
  Item(int idx, int face, int height) : p(idx, face), height(height) {}
  bool operator<(const Item& other) const {
    return height < other.height;
  }
};

const char *names[] = {
  "front",
  "back",
  "left",
  "right",
  "top",
  "bottom"
};


int main() {
  setvbuf(stdin, NULL, _IOFBF, 10000);
  setvbuf(stdout, NULL, _IOFBF, 10000);
  Cube cubes[1024];
  Item tallest[256];
  Item tmp[256];
  int n;
  int ctr = 0;
  while (scanf("%d", &n) == 1 && n) {
    if (ctr > 0) putchar('\n');
    fill(tallest, tallest+256, Item());
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < 6; ++j) {
        scanf("%d", &cubes[i].colors[j]);
      }
      fill(cubes[i].preds, cubes[i].preds+6, Pair());
    }
    for (int i = n-1; i >= 0; --i) {
      Cube& cube = cubes[i];
      for (int j = 0; j < 6; ++j) {
        tmp[cube.colors[j]] = tallest[cube.colors[j]];
      }
      for (int j = 0; j < 6; ++j) {
        int top = cube.colors[j];
        int bot = cube.colors[j + ((j%2) ? -1 : 1)];
        int new_height = tallest[bot].height + 1;
        if (new_height > tmp[top].height) {
          tmp[top].p.idx = i;
          tmp[top].p.face = j;
          tmp[top].height = new_height;
          cube.preds[j].idx = tallest[bot].p.idx;
          cube.preds[j].face = tallest[bot].p.face;
        }
      }
      for (int j = 0; j < 6; ++j) {
        tallest[cube.colors[j]] = tmp[cube.colors[j]];
      }
    }
    Item* max_el = max_element(tallest, tallest+256);
    printf("Case #%d\n", ctr+1);
    printf("%d\n", max_el->height);
    for (Pair p = max_el->p; p.idx != -1; p = cubes[p.idx].preds[p.face]) {
      printf("%d %s\n", p.idx+1, names[p.face]);
    }
    ++ctr;
  }
  
  return 0;
}