Computer Programming Contest Preparation

    1 #include <stdio.h>
    2 #include <strings.h>
    3 #include <sys/types.h>
    4 #include <sys/stat.h>
    5 #include <fcntl.h>
    6 #include <stdlib.h>
    7 #include <string.h>
    8 
    9 #define TRUE  (1 == 1)
   10 #define FALSE (1 != 1)
   11 
   12 #define DEBUG if (FALSE)
   13 #define DEBUG2 if (FALSE)
   14 
   15 #define MAX_LENGTH 30
   16 
   17 /* fprintf(stderr, "functionName: message", varslist); */
   18 
   19 /*
   20  *  Author:
   21  *    Date: 2005 08 03
   22  * Purpose: practice
   23  * Problem: 10460
   24  */
   25 
   26 /*
   27  * This template reads data a specified number of times.
   28  */
   29 
   30 int numberOfTimes;
   31 unsigned int Ith;
   32 char perm[MAX_LENGTH];
   33 char result[MAX_LENGTH];
   34 
   35 void init()
   36 {
   37     /* FUNCTION init */
   38     scanf("%d ", &numberOfTimes);
   39 } /* FUNCTION init */
   40 
   41 void dump()
   42 {
   43     /* FUNCTION dump */
   44     printf("Ith=(%d)\t\tString=(%s)\n", Ith, perm);
   45 } /* FUNCTION dump */
   46 
   47 void getInput()
   48 {
   49     /* FUNCTION getInput */
   50     scanf(" %s ", perm);
   51     scanf(" %u ", &Ith);
   52 } /* FUNCTION getInput */
   53 
   54 int fact(int input)
   55 {
   56     /* FUNCTION fact */
   57     int i;
   58     int result = 1;
   59 
   60     for (i = 1; i <= input; i++)
   61         {
   62             result = result * i;
   63         }
   64 
   65     return result;
   66 } /* FUNCTION fact */
   67 
   68 void insertChar(int offset, int source)
   69 {
   70     int target = 0;
   71     int i;
   72 
   73     DEBUG2 printf("pre-insert: \"%s\"\n", result);
   74 
   75     for (i = 0; i < offset; i++)
   76         {
   77             while (' ' != result[target])
   78                 {
   79                     target++;
   80                 }
   81 
   82             target++;
   83         }
   84 
   85     while (' ' != result[target])
   86         {
   87             target++;
   88         }
   89 
   90     result[target] = perm[source];
   91 
   92     DEBUG2 printf("post-insert: \"%s\"\n", result);
   93 }
   94 
   95 void process()
   96 {
   97     /* FUNCTION process */
   98     int permLen;
   99     int divisor = 1;
  100     int modder;
  101     int ans;
  102     int source;
  103 
  104     memset(result, ' ', sizeof(result));
  105     result[MAX_LENGTH - 1] = '\0';
  106     permLen = strlen(perm);
  107     modder = permLen;
  108     source = permLen - 1;
  109 
  110     while (1 < modder)
  111         {
  112             ans = ((Ith - 1) / divisor) % modder;
  113 
  114             DEBUG2 printf("ans: %d\n", ans);
  115             DEBUG2 printf("perm[source]: %c\n", perm[source]);
  116             insertChar(ans, source);
  117 
  118             divisor *= modder;
  119             modder--;
  120             source--;
  121         }
  122 
  123     /* insert the first character in the first available spot */
  124     insertChar(0, 0);
  125 
  126     result[permLen] = '\0';
  127 
  128     printf("%s\n", result);
  129 } /* FUNCTION process */
  130 
  131 int main ()
  132 {
  133     /* main */
  134     int i;
  135 
  136     init();
  137     for (i=0; i<numberOfTimes; i++)
  138         {
  139             /* while */
  140             getInput();
  141             DEBUG dump();
  142             process();
  143         } /* while */
  144 
  145     return EXIT_SUCCESS;
  146 } /* main */
  147