Computer Programming Contest Preparation

    1 #include <stdio.h>
    2 #include <stdlib.h>
    3 
    4 /*
    5  *  Author: Damir Hasic
    6  *    Date: 2004-09-19
    7  * Purpose: Contest practice
    8  * Problem: 299 - Train Swapping <http://isaac.lsu.edu/udv/v2/299.html>
    9  */
   10 
   11 #define MAX_TRAIN_LENGTH 50
   12 
   13 int trains[MAX_TRAIN_LENGTH + 1];
   14 
   15 void swap(int y)
   16 {
   17     int temp;
   18 
   19     temp = trains[y];
   20     trains[y] = trains[y+1];
   21     trains[y+1] = temp;
   22 }
   23 
   24 void Process(int L)
   25 {
   26     int x, y, swaps;
   27 
   28     swaps = 0;
   29     for (x = 0; x < L - 1; x++)
   30         {
   31             for (y = 0; y < L - 1 - x; y++)
   32                 {
   33                     if (trains[y] > trains[y+1])
   34                         {
   35                             swap(y);
   36                             swaps++;
   37                         }
   38                 }
   39         }
   40 
   41     printf("Optimal train swapping takes %d swaps.\n", swaps);
   42 }
   43 
   44 int main()
   45 {
   46     int N, num, i, j, L;
   47 
   48     scanf("%d", &N);
   49     for(i = 0; i < N; i++)
   50         {
   51             scanf("%d", &L);
   52             for (j = 0; j < L; j++)
   53                 {
   54                     scanf("%d", &num);
   55                     trains[j] = num;
   56                 }
   57             Process(L);
   58         }
   59 
   60     return EXIT_SUCCESS;
   61 }
   62 
   63