/*--------------------------------------------*\
                |                                              |
                |   acm / optimal.c                            |
                |   ~~~~~~~~~~~~~~~                            |
                |   Erstellt: 11. 9.1998                       |
                |   Geändert: 25. 9.1998                       |
                |                                              |
                \*--------------------------------------------*/

#ifdef LINUX
#  ifdef X
#    define ROT    "\033[0;31m"         /* WRA */
#    define GELB   "\033[0;33m"         /* PRE */
#    define GRUEN  "\033[0;32m"         /* ACC */
#    define NORMAL "\033[0m"            /* reset terminal */
#  else
#    define ROT    "\033[1;31m"         /* WRA */
#    define GELB   "\033[1;33m"         /* PRE */
#    define GRUEN  "\033[1;32m"         /* ACC */
#    define NORMAL "\033[0m"            /* reset terminal */
#  endif
#else
#  define ROT
#  define GELB
#  define GRUEN
#  define NORMAL
#endif



/* Contest:   SWERC 1998 Ulm
 * Problem A: optimal
 * Methode:   backtracking   generate and test
 * Author:    Thorsten
 * Date:      11. Sep 1998 - 24. Sep 1998, 31. Oct 1998
 */

#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

#define max_length    10
#define max_samples   10
#define max_value  30000
#define min_value -30000

#define ADD 0
#define SUB 1
#define MUL 2
#define DIV 3
#define DUP 4

       FILE * input;
       char * mnemonic[] = { "ADD", "SUB", "MUL", "DIV", "DUP" };
       int    kase = 0;
static int    program[max_length+2];
       int    length;
static int    samples[max_samples+2][2];
       int    nsamples;

#ifdef COUNT
       int    count;
#endif

int test ()
{
  static int stack[max_length/2+2];
  int sample, pos, stack_pointer;

#ifdef COUNT
  count++;
#endif

  for (sample = 0; sample < nsamples; sample++)
  {
    stack[stack_pointer=0] = samples[sample][0];
    for (pos = 0; pos < length; pos++)
    {
      switch (program[pos]) {
        case ADD: stack[stack_pointer-1] += stack[stack_pointer];
                  stack_pointer--; break;
        case SUB: stack[stack_pointer-1] -= stack[stack_pointer];
                  stack_pointer--; break;
        case MUL: stack[stack_pointer-1] *= stack[stack_pointer];
                  stack_pointer--; break;
        case DIV: if (stack[stack_pointer] == 0)
                  stack[stack_pointer-1]  = max_value+1; else
                  stack[stack_pointer-1] /= stack[stack_pointer];
                  stack_pointer--; break;
        case DUP: stack[stack_pointer+1]  = stack[stack_pointer];
                  stack_pointer++; break;
      }
      assert (stack_pointer >= 0);
      if (stack[stack_pointer] < min_value) break;
      if (stack[stack_pointer] > max_value) break;
    }
    if (pos < length) return 0;                   /* RTE */
    assert (stack_pointer == 0);
    if (stack[0] != samples[sample][1]) return 0; /* WRA */
  }
  return 1;                                       /* ACC */
}

int generate (int pos, int stack_pointer)
{
                      if (stack_pointer < 0)                 return 0;
                      if (stack_pointer > length - pos)      return 0;
                      if (pos == length)                     return test ();
  program[pos] = ADD; if (generate (pos+1, stack_pointer-1)) return 1;
  program[pos] = DIV; if (generate (pos+1, stack_pointer-1)) return 1;
  program[pos] = DUP; if (generate (pos+1, stack_pointer+1)) return 1;
  program[pos] = MUL; if (generate (pos+1, stack_pointer-1)) return 1;
  program[pos] = SUB; if (generate (pos+1, stack_pointer-1)) return 1;
                                                             return 0;
}

void write_case ()
{
  int fl = 0, pos;
#ifdef COUNT
  printf ("%8d   ", count);
#endif
  printf ("Program %d\n", ++kase);
  if (length > max_length) printf ("Impossible"); else
  if (length == 0) printf ("Empty sequence"); else
  for (pos = 0; pos < length; pos++)
    printf ("%s%s", fl++ ? " " : "", mnemonic[program[pos]]);
  puts ("\n");
}

void solve_case ()
{
#ifdef COUNT
  count = 0;
#endif
  for (length = 0; length <= max_length && !generate (0, 0); length += 2);
}

int read_case ()
{
  int sample;

  fscanf (input, "%d", &nsamples);
  
  for (sample = 0; sample < nsamples; sample++)
    fscanf (input, "%d", &samples[sample][0]);

  for (sample = 0; sample < nsamples; sample++)
    fscanf (input, "%d", &samples[sample][1]);

  return nsamples;
}

#ifndef JUDGE

int main ()
{
  input = fopen ("optimal.in", "r");
  assert (input);
  while (read_case ()) { solve_case (); write_case (); }
  fclose (input);
  return 0;
}

#else

#define CHOP(s) if (*s) s[strlen(s)-1] = 0
#define ACC 0
#define WRA 1
#define PRE 2

FILE * output;
char * W, * P;
int L;

int judge_case ()
{
  static char s[256];
  static char d[256];
  int p;
  bzero (s, 256);
  fgets (s, 256, output);
  CHOP (s);
  if (length > max_length)
  {
    if (!strcmp (s, "<impossible>"))               { if (!W) L++; return ACC; }
    if (s[0] == '<' || s[2] == 'm' || s[2] == 'M') { P=strdup(s); return PRE; }
                                                     W=strdup(s); return WRA;
  }
  if (isalnum (s[length*4]))                       { W=strdup(s); return WRA; }
  for (p = 0; p < length; p++)
    switch (toupper (s[p*4])) {
      case 'A': program[p] = ADD; break;
      case 'S': program[p] = SUB; break;
      case 'M': program[p] = MUL; break;
      case 'D': if (s[p*4+1] == 'I') { program[p] = DIV; break; }
                if (s[p*4+1] == 'U') { program[p] = DUP; break; }
                                                     W=strdup(s); return WRA;
      default:                                       W=strdup(s); return WRA;
    }
  if (!test ())                                    { W=strdup(s); return WRA; }
  d[0]=0;
  for (p = 0; p < length; p++)
    sprintf (d+p*4, "%s ", mnemonic[program[p]]);
  CHOP(d);
  if (strcmp (s, d))                               { P=strdup(s); return PRE; }
  if (s[strlen(s)-1] == ' ')                       { P=strdup(s); return PRE; }
                                                     if (!W) L++; return ACC;
}

int main ()
{
  int reply;
  input = fopen ("optimal.in", "r");
  assert (input);
  output = fopen ("optimal.out", "r");
  assert (output);
  reply = ACC; W = P = NULL; L = 1;
  while (read_case () && !(reply & WRA)) solve_case (), reply |= judge_case ();
  fclose (output);
  fclose (input);
  switch (reply) {
    case ACC: puts   (GRUEN "# Suggest \"Accepted\" (ACC)" NORMAL);     break;
    case PRE: printf (GELB "# \"%s\"\n", P);
              puts   ("# Suggest \"Presentation Error\" (PRE)" NORMAL); break;
    case PRE+WRA:
    case WRA: printf (ROT "# Case: %d\n# \"%s\"\n", L, W);
              puts   ("# Suggest \"Wrong Answer\" (WRA)" NORMAL);       break;
  }
  if (W) free (W);
  if (P) free (P);
  return 0;
}

#endif