1 #include <stdio.h>
    2 #include <stdlib.h>
    3 #include <math.h>
    4 
    5 #define MAX_PROBS	1000
    6 
    7 int pWid;
    8 char inbuf[256];
    9 
   10 int maxval = 16384 * 8192;
   11 
   12 int F[101], G[101], H[101];
   13 
   14 int compVals()
   15 {
   16   int i;
   17   F[0] = 1;
   18   F[1] = 1;
   19   G[0] = 0;
   20   G[1] = 1;
   21   H[0] = 0;
   22   H[1] = 1;
   23   for (i = 2; i < 101 ; i++)
   24     {
   25       F[i] = F[i-1] + F[i-2] + G[i-1] + 2*H[i-1];
   26       G[i] = F[i-1] + G[i-2];
   27       H[i] = F[i-1] + H[i-1];
   28       if (F[i] >= maxval)
   29         {
   30           return i;
   31         }
   32     }
   33   return 100;
   34 }
   35 
   36 /*
   37  * F[n] = number of ways to tile a 4-by-n grid
   38  * G[n] = number of ways to tile a 4-by-n grid with top-right and bottom-right
   39  *			squares uncovered
   40  * H[n] = number of ways to tile a 4-by-n grid with bottom-right 2
   41  *			squares uncovered
   42  *      = number of ways to tile a 4-by-n grid with top-right 2
   43  *			squares uncovered
   44  * if n >= 2, the right end of any tiling can be
   45  *	two vertical dominoes (F[n-1] ways)
   46  *	horz, horz vert (H[n-1] ways)
   47  *	horz, vert, horz (G[n-1] ways)
   48  *	vert, horz, horz (H[n-1] ways)
   49  *	4 horizontal dominoes (F[n-2] ways)
   50  * F[n] = F[n-1] + G[n-1] + 2*H[n-1] + F[n-2];
   51  * For G: the right end can be a vertical domino (F[n-1] ways)
   52  *		or two horizontal dominoes => top & bottom are horz = G[n-2]
   53  *		G[n] = F[n-1] + G[n-2];
   54  * For H: the right end can be a vertical domino (F[n-1] ways)
   55  *		or two horizontal dominoes (H[n-1] ways)
   56  *		H[n] = F[n-1] + H[n-1];
   57  * F[0] = 1, F[1] = 1, G[0] = 0, G[1] = 1, H[0] = 0, H[1] = 1
   58  */
   59 int main()
   60 {
   61   int probCnt, curProb, ret;
   62 
   63   ret = compVals();
   64   /*	printf("compVals ret %d F = %d\n", ret, F[ret]); */
   65   if (fgets(&(inbuf[0]), 255, stdin) == NULL)
   66     {
   67       fprintf(stderr, "read failed on problem count\n");
   68       return -1;
   69     }
   70   inbuf[255] = 0;
   71   probCnt = atoi(&(inbuf[0]));
   72   if ((probCnt < 1) || (probCnt > MAX_PROBS))
   73     {
   74       fprintf(stderr, "Problem count %d not in range 1...%d\n", probCnt, MAX_PROBS);
   75       return -2;
   76     }
   77   for (curProb = 1; curProb <= probCnt ; curProb++)
   78     {
   79       if (fgets(&(inbuf[0]), 255, stdin) == NULL)
   80         {
   81           fprintf(stderr, "read failed on problem %d\n", curProb);
   82           return -3;
   83         }
   84       if (sscanf(&(inbuf[0]), "%d", &pWid) != 1)
   85         {
   86           fprintf(stderr, "scan failed on problem %d\n", curProb);
   87           return -4;
   88         }
   89       if (pWid > ret)
   90         {
   91           fprintf(stderr, "width %d too large problem %d\n", pWid, curProb);
   92           return -5;
   93         }
   94       printf("%d %d\n", curProb, F[pWid]);
   95     }
   96   return 0;
   97 }
   98