/* Solution checker for the Nullary problem from NCPC 2005.
 *
 * The checker expects a nullary program to be checked on standard input.
 * 
 * The checker will write information about the result to standard
 * out, and return the result as an exit code (useful for automatic
 * validation).
 *
 * When given the command-line parameter '-c', the checker only
 * performs a compilation of the nullary program (so the possible exit
 * codes are 0 and 4, see below).
 *
 * Exit codes: 0: Accepted
 *             1: Wrong Answer
 *             2: Run Time Error
 *             3: Time Limit Exceeded
 *             4: Compile Error
 *
 * Author: Per Austrin
 */

#include <ctype.h>

/* Set non-zero to print additional (internal) judging information. */
const int debug = 0;

/* Parameters from the problem statement. */
const int MAX_NITS = 64;
const int CODE_SIZE_LIMIT = 5432;

/* Parameters controlling the test cases. */
const int RUNTIME_LIMIT = 5000000;
const int TEST_CASE_COUNT = 100;
const int RANDOM_SEED = 12345689;




/* Various return messages. */
const char *compile_msgs[] = {"compilation OK",
			      "unbalanced parenthesises",
			      "invalid symbol in source code",
			      "code size limit exceeded"};
const char *run_msgs[] = {"Accepted",
			  "Wrong Answer",
			  "Run Time Error",
			  "Time Limit Exceeded"};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char program[10000];
int jump[10000];


/** "Compile" the Nullary program (set up jump table)
 * Returns 0 on compilation OK,
 *         1 on unbalanced parenthesis error
 *         2 on invalid symbol error
 *         3 on code size limit exceeded
 */
int compile() {
  int s[10000], l = 0, i;

  if (strlen(program) > CODE_SIZE_LIMIT) return 3;

  for (i = 0; program[i]; ++i) {
    char p = program[i];
    if (p == '(') {
      s[l++] = i;
    } else if (p == ')') {
      if (!l--) return 1;
      jump[i] = s[l];
      jump[s[l]] = i;
    } else if (!((p >= 'A' && p <= 'Z') || 
		 (p >= 'a' && p <= 'z')))
      return 2;
  }
  if (l) return 1; /* Check for straggling parenthesises. */
  return 0;
}

/* Run the program on the current contents of the registers.
 * Returns 0 if run finished
 *         1 if max number of nits exceeded
 *         2 if number of operations exceeded maxops
 */
int run(int registers[26], int maxops) {
  int pos = 0, flag = 0, ops = 0;
  while (program[pos] && ops < maxops) {
    char p = program[pos];
    if (p == '(') {
      if (flag) flag = 0;
      else pos = jump[pos];
    } else if (p == ')') {
      pos = jump[pos]-1;
    } else if (p >= 'A' && p <= 'Z') {
      ++registers[p-'A'];
      if (registers[p-'A'] > MAX_NITS) {
	if (debug) {
	  fprintf(stderr, "Runtime error on op %d pos %d reg %c\n",
		  ops, pos, p);
	}
	return 1;
      }
    } else if (p >= 'a' && p <= 'z') {
      flag = 0;
      if (registers[p-'a']) {
	flag = 1;
	--registers[p-'a'];
      }
    }
    ++pos;
    ++ops;
  }
  return program[pos] ? 2 : 0;
}

int int_cmp(const void *a, const void *b) {
  return *(int*)a - *(int*)b;
}

/* Run sorting program tests.
 * Returns 0 if Accepted
 *         1 on Wrong Answer
 *         2 on Run Time Error
 *         3 on Time Limit Exceeded
 */
int run_sort_tests(int count) {
  int i, j, cse, ret_code, registers[26], answer[26];
  int ans = 0;
  for (cse = 1; cse <= count; ++cse) {
    /* First, take a few special cases. */
    switch (cse) {
    case 1: /* Input is already sorted. */
      for (i = 0; i < 24; ++i) registers[i] = 40+i;
      break;
    case 2: /* Input is in decreasing order. */
      for (i = 0; i < 24; ++i) registers[i] = 64-i;
      break;
    case 3: /* All input values the same and maximal. */
      for (i = 0; i < 24; ++i) registers[i] = 64;
      break;
    case 4: /* All input values the same and minimal. */
      memset(registers, 0, sizeof(registers));
      break;
    default:
      for (i = 0; i < 24; ++i) registers[i] = rand() % (MAX_NITS+1);
    }
    registers[24] = registers[25] = 0;

    /* Compute correct answer. */
    memcpy(answer, registers, sizeof(answer));
    qsort(answer, 24, sizeof(int), int_cmp);

    fprintf(stderr, "Running case %d/%d\n", cse, count);
    
    ret_code = run(registers, RUNTIME_LIMIT);

    /* On RTE or TLE, we are done. */
    if (ret_code) return ret_code+1;

    /* Check answer, but only if we haven't gone wrong already. */
    if (!ans) {
      for (i = 0; i < 26; ++i)
	if (answer[i] != registers[i]) {
	  if (debug) {
	    fprintf(stderr, "Wrong answer.\n");
	    fprintf(stderr, "Correct answer  :");
	    for (j = 0; j < 26; ++j)
	      fprintf(stderr, " %2d", answer[j]);
	    fprintf(stderr, "\nRegister content:");
	    for (j = 0; j < 26; ++j)
	      fprintf(stderr, " %2d", registers[j]);
	    fprintf(stderr, "\n");
	  }
	  /* On wrong answer, we should still run the remaining test
	   * cases since RTE and TLE have higher priority. */
	  ans = 1;
	  break;
	}
    }
  }
  return ans;
}

int main(int argc, char **argv) {
  int result;
  int compile_only = 0;
  int i;
  char *prg = program, c;

  for (i = 1; i < argc; ++i) {
    if (!strcmp(argv[i], "-c")) {
      compile_only = 1;
    }
  }

  srand(RANDOM_SEED);

  /* Read the program, ignoring whitespace. */
  while ((c = getchar()) != EOF && prg < program + 8192) {
    if (!isspace(c)) *prg++ = c;
  }
  *prg = 0;

  /* Compile the program. */
  result = compile();
  if (result) {
    printf("Judge verdict: 'Compile Error'\n");
    if (debug) {
      fprintf(stderr, "(%s)\n", compile_msgs[result]);
    }
    return 4;
  }

  if (compile_only) {
    printf("Compilation succeeded.\n");
    return 0;
  }

  result = run_sort_tests(TEST_CASE_COUNT);

  printf("Judge verdict: '%s'\n", run_msgs[result]);
  return result;
}