1 #include <stdio.h>
    2 #include <stdlib.h>
    3 #include <ctype.h>
    4 
    5 #define MAX_PROBS	1000
    6 #define MAX_PANCAKES	30
    7 
    8 char inbuf[256];
    9 int nPancakes;
   10 int pancakes[MAX_PANCAKES];
   11 int moves[3*MAX_PANCAKES];
   12 int curLoc[MAX_PANCAKES+1];
   13 
   14 int parseInput(char *pIn)
   15 {
   16   char *p;
   17   int i, ret, val, ind;
   18   /* get number of pancakes */
   19   p = pIn;
   20   while ((*p != 0) && (isspace(*p))) p++;
   21   if (*p == 0)
   22     {
   23       return -2;
   24     }
   25   ret = atoi(p);
   26   if ((ret < 1) || (ret > MAX_PANCAKES))
   27     {
   28       return -1;
   29     }
   30   for (i = 1; i <= ret; i++) curLoc[i] = 0;
   31   /* read ret pancakes */
   32   for (i = 0; i < ret ; i++)
   33     {
   34       /* skip past prev item */
   35       while ((*p != 0) && (!isspace(*p))) p++;
   36       while ((*p != 0) && (isspace(*p))) p++;
   37       if (*p == 0)
   38         {
   39           return -2;
   40         }
   41       if ((*p != '+') && (*p != '-'))
   42         {
   43           return -3;
   44         }
   45       val = atoi(p);
   46       if ((val == 0) || (val < -ret) || (val > ret))
   47         {
   48           return -4;
   49         }
   50       ind = abs(val);
   51       if (curLoc[ind] != 0)
   52         {
   53           return -5;
   54         }
   55       pancakes[i] = val;
   56       curLoc[ind] = i+1;
   57     }
   58   /* check all seen */
   59   for (i = 1; i <= ret; i++)
   60     {
   61       if (curLoc[i] == 0)
   62         {
   63           return -6;
   64         }
   65     }
   66   nPancakes = ret;
   67   return ret;
   68 }
   69 
   70 /* flip top k pancakes */
   71 void flip(int k)
   72 {
   73   int i, j, tmp;
   74   i = 0;
   75   j = k-1;
   76   while (i < j)
   77     {	/* swap values and change signs */
   78       tmp = -pancakes[i];
   79       pancakes[i] = -pancakes[j];
   80       pancakes[j] = tmp;
   81       i++;
   82       j--;
   83     }
   84   if (i == j)
   85     {
   86       pancakes[i] = -pancakes[i];
   87     }
   88   /* fix locations */
   89   for (i = 1; i <= nPancakes; i++)
   90     {
   91       if (curLoc[i] <= k)
   92         {
   93           curLoc[i] = k + 1 - curLoc[i];
   94         }
   95     }
   96 }
   97 
   98 /* for each size from largest to smallest, if not correct, flip to top
   99  * make burned side up, flip to correct position
  100  */
  101 int FindSoln()
  102 {
  103   int curPk, curStep;
  104 
  105   curStep = 0;
  106   for (curPk = nPancakes ; curPk > 0 ; curPk--)
  107     {
  108       if ((curLoc[curPk] != curPk) || (pancakes[curLoc[curPk]-1] < 0))
  109         {	/* not in correct place or correct orientation */
  110           if (curPk > 1)
  111             {
  112               /* flip from cur loc to top */
  113               if (curLoc[curPk] != 1)
  114                 {
  115                   moves[curStep++] = curLoc[curPk];
  116                   flip(curLoc[curPk]);
  117                 }
  118               if (pancakes[0] > 0)
  119                 {
  120                   moves[curStep++] = 1;
  121                   flip(1);
  122                 }
  123               moves[curStep++] = curPk;
  124               flip(curPk);
  125             }
  126           else
  127             {
  128               moves[curStep++] = 1;
  129               flip(1);
  130             }
  131         }
  132     }
  133   return curStep;
  134 }
  135 
  136 /* print nStep followed by nStep moves */
  137 void PrintSoln(int probNum, int nStep)
  138 {
  139   int i;
  140   printf("%d %d", probNum, nStep);
  141   for (i = 0; i < nStep ; i++)
  142     {
  143       printf(" %d", moves[i]);
  144     }
  145   printf("\n");
  146 }
  147 
  148 int main()
  149 {
  150   int probCnt, curProb, ret;
  151 
  152   if (fgets(&(inbuf[0]), 255, stdin) == NULL)
  153     {
  154       fprintf(stderr, "read failed on problem count\n");
  155       return -1;
  156     }
  157   inbuf[255] = 0;
  158   probCnt = atoi(&(inbuf[0]));
  159   if ((probCnt < 1) || (probCnt > MAX_PROBS))
  160     {
  161       fprintf(stderr, "Problem count %d not in range 1...%d\n", probCnt, MAX_PROBS);
  162       return -2;
  163     }
  164   for (curProb = 1; curProb <= probCnt ; curProb++)
  165     {
  166       if (fgets(&(inbuf[0]), 255, stdin) == NULL)
  167         {
  168           fprintf(stderr, "read failed on problem %d\n", curProb);
  169           return -3;
  170         }
  171       if ((ret = parseInput(&(inbuf[0]))) < 0)
  172         {
  173           fprintf(stderr, "parseInput returned %d on problem %d\n", ret, curProb);
  174           return -4;
  175         }
  176       ret = FindSoln();
  177       PrintSoln(curProb, ret);
  178     }
  179   return 0;
  180 }
  181 
  182 
  183 
  184 
  185 
  186 
  187 
  188 
  189 
  190 
  191 
  192 
  193 
  194 
  195 
  196 
  197 
  198 
  199 
  200 
  201 
  202 
  203 
  204