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 
   14 #define MAX_LENGTH 30
   15 
   16 /* fprintf(stderr, "functionName: message", varslist); */
   17 
   18 /*
   19  *  Author:
   20  *    Date: 2005 08 03
   21  * Purpose: practice
   22  * Problem: 10460
   23  */
   24 
   25 /*
   26  * This template reads data a specified number of times.
   27  */
   28 
   29 int numberOfTimes;
   30 int Ith;
   31 char perm[MAX_LENGTH];
   32 char result[MAX_LENGTH];
   33 int upper;
   34 int lower;
   35 
   36 int init()
   37 {
   38     /* FUNCTION init */
   39     scanf("%d ", &numberOfTimes);
   40 } /* FUNCTION init */
   41 
   42 void dump()
   43 {
   44     /* FUNCTION dump */
   45     printf("Ith=(%d)\t\tString=(%s)\n", Ith, perm);
   46 } /* FUNCTION dump */
   47 
   48 void getInput()
   49 {
   50     /* FUNCTION getInput */
   51     scanf(" %s ", perm);
   52     scanf(" %d ", &Ith);
   53 } /* FUNCTION getInput */
   54 
   55 int fact(int input)
   56 {
   57     /* FUNCTION fact */
   58     int i;
   59     int result = 1;
   60 
   61     for (i = 1; i <= input; i++)
   62         {
   63             result = result * i;
   64         }
   65 
   66     return result;
   67 } /* FUNCTION fact */
   68 
   69 void insertChar(int sourcePos, int destPos)
   70 {
   71     int i;
   72     int length;
   73 
   74     length = strlen(result);
   75     for (i = length + 1; i >= destPos; i--)
   76         {
   77             result[i+1] = result[i];
   78         }
   79 
   80     result[destPos] = perm[sourcePos - 1];
   81 }
   82 
   83 void placeNext (int next)
   84 {
   85     /* FUNCTION placeNext */
   86     int delta;
   87     int magic;
   88 
   89     delta = (1 + upper - lower) / next;
   90     DEBUG printf("delta: %d\n", delta);
   91     if (0 == delta)
   92         {
   93             printf("PANIC!!! delta = 0\n");
   94             return;
   95         }
   96 
   97     magic = (Ith - lower - 1) / delta;
   98     DEBUG printf("magic: %d\n", magic);
   99     lower = lower + magic * delta;
  100     upper = lower + delta - 1;
  101 
  102     insertChar(next, magic);
  103 
  104     DEBUG printf("lower: %d\n", lower);
  105     DEBUG printf("upper: %d\n", upper);
  106     DEBUG printf("\n");
  107 
  108     DEBUG printf("result: \"%s\"\n", result);
  109 } /* FUNCTION placeNext */
  110 
  111 void process()
  112 {
  113     /* FUNCTION process */
  114     int permLen;
  115     int i;
  116 
  117     result[0] = perm[0];
  118     result[1] = '\0';
  119 
  120     permLen = strlen(perm);
  121     lower = 0;
  122     upper = fact(permLen);
  123     for (i = 2; i <= permLen; i ++)
  124         {
  125             /* for */
  126             placeNext(i);
  127         } /* for */
  128 
  129     printf("%s\n", result);
  130 } /* FUNCTION process */
  131 
  132 int main ()
  133 {
  134     /* main */
  135     int i;
  136 
  137     init();
  138     for (i=0; i<numberOfTimes; i++)
  139         {
  140             /* while */
  141             getInput();
  142             DEBUG dump();
  143             process();
  144         } /* while */
  145 
  146     return EXIT_SUCCESS;
  147 } /* main */
  148