#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define TRUE 1
#define FALSE 0
#define MAX_STRING 100
#define MAX_TEAMS 16

typedef
struct t_element {
   char Name[MAX_STRING];
   char Mascot[MAX_STRING];
   float Offense;
   int Defense;
   struct t_element *next;
} element_t;

void ReadTeams(void);
void ReadString(char string[MAX_STRING]);
void ReadInt(int *theinteger);
void ReadComma(void);
void ReadEOL(void);
void SortTeams(void);
void OrderBracket(void);
void PlayTournament(void);
void PrintTeams(void);
void PrintTeamsArray(void);

FILE *infile = NULL,
     *outfile = NULL;

/* Here are globals for the team list */
element_t *TeamList = NULL;

element_t *TeamArray[MAX_TEAMS];
int ArraySize = -1;

int FoundEOF;
int numTeams = 0;

int
main (void) {
   /* Open the input file */
   infile = fopen("tournament.in","r");
   if (infile == NULL) {
      fprintf(stderr,"Couldn't open the input file\n");
      exit(-1);
   }

   FoundEOF = FALSE;

   while (!FoundEOF) {
      /* Read in the list of teams */
      ReadTeams();
      /** DEBUG: Print the list of teams **/
      //PrintTeams();
      /* Sort the teams by seed */
      SortTeams();

      /** DEBUG: Print the list of teams **/
      //PrintTeams();
      /* Re-arrange teams for play-off ordering */
      OrderBracket();

      /** DEBUG: Print the list of teams **/
      //PrintTeams();

      /* Play the tournament */
      PlayTournament();
   }
   /* Return */
   return 0;

}

void PlayTournament(void) {

   int score1, score2, temp;
   int index, windex, losedex;
   int numprevgames, numcurgames;

   /* We will loop through the list, playing adjacent teams. */
   /* When we're down to 2 teams, we're done! */

   numcurgames=ArraySize;
   while (numcurgames > 1) {
      numprevgames = numcurgames;
      numcurgames = 0;
      for (index=0; index < numprevgames; index+=2) {

         /* Increment the number of games... */
         ++numcurgames;

         /* Play the next two teams... */
         score1 = floor(
                  TeamArray[index]->Offense * 5 -
                  TeamArray[index+1]->Defense * 2 + 0.5);
         score2 = floor(
                  TeamArray[index+1]->Offense * 5 -
                  TeamArray[index]->Defense * 2 + 0.5);

         /* Delete the loser */
         if (score1>score2) {
            windex = index;
            losedex = index+1;
         } else if (score2>score1) {
            windex = index+1;
            losedex = index;
         } else {
            if (strcmp(TeamArray[index]->Mascot,TeamArray[index+1]->Mascot) < 0){
               windex = index;
	       losedex = index+1;
	    }
	    else {
	       windex = index+1;
	       losedex = index;
	    }
         }

         /* Check for big winning margin */
         /* Increase the winner's offense, but don't worry about */
         /* the loser.  This is single-elimination! */
         if (abs(score1-score2) > 10) {
            TeamArray[windex]->Offense += .5;
	    //printf("Increased %s",TeamArray[windex]->Mascot);
         }

         /* Delete the loser */
         free(TeamArray[losedex]);
         TeamArray[losedex] = NULL;

         /* Put the winner in the correct position in the array */
         TeamArray[index/2] = TeamArray[windex];

      } /* end for each game */
   } /* end while no winner */

   /* Alright, we have a winner! */

   /* Print out the winner's info */
   if (score2 > score1) {
      temp = score1;
      score1 = score2;
      score2 = temp;
   }
   fprintf(stdout,"%s %d-%d\n",TeamArray[0]->Name,score1,score2);
   free(TeamArray[0]);
   TeamArray[0] = NULL;
   TeamList = NULL;
}

void OrderBracket(void) {

   element_t *temp;
   int index;
   int half;
   int even_count = 0, 
        odd_count = 0;

   element_t *TempArray[MAX_TEAMS];

   /* This should be fun. */
   /* From a list like this: */
   /* 8 7 6 5 4 3 2 1 */
   /* We need to create a new list where it goes like this: */
   /* 8 1 7 2 6 3 5 4 */
   /* Let's do it with an array! */   

   /* Init the array. */
   memset(TempArray,0,sizeof(element_t *)*MAX_TEAMS);
   memset(TeamArray,0,sizeof(element_t *)*MAX_TEAMS);

   /* Load the current values */
   temp = TeamList;
   index = 0;
   while(temp != NULL) {
      TempArray[index++]=temp;
      temp=temp->next;
   }   
   ArraySize = index;

   /* Re-arrange the array */
   for (index = 0; index < ArraySize; index++) {
      if (index % 2 == 0) {
         /* An even index */
         TeamArray[even_count*2]=TempArray[even_count];
         ++even_count;
      } else {
         /* An odd index */
         TeamArray[odd_count*2+1]=TempArray[(ArraySize-1)-odd_count];
         ++odd_count;
      }
   }

   /** DEBUG - re-arrange the linked list too (for printing) **/
   TeamList=TeamArray[0];
   temp = TeamList;
   for (index = 1; index < ArraySize; index++) {
      temp->next=TeamArray[index];
      temp=temp->next;
   }
   temp->next=NULL;

   /* Return */
   return;
}

void SortTeams(void) {

   int swapped = TRUE;
   element_t **current, *temp;

   /* Sort the teams by offensive rating...        */
   /* We'll use a bubble sort.                     */
   /* It's inefficient, but it's easy to write and */
   /* efficient enough on small data sets          */

   /* While we have swapped, go through the list again */
   while (swapped == TRUE) {

      swapped = FALSE;

      /* Go through the list */
      current = &TeamList;

      while ((*current)->next != NULL) {

         /* Check if these elements are in the right order */
         if ((*current)->Offense < (*current)->next->Offense ||
             ((*current)->Offense == (*current)->next->Offense &&
              strcmp((*current)->Mascot,(*current)->next->Mascot) < 0
            )) {

            /* We should swap these... */
            temp = (*current);
            (*current)=(*current)->next;
            temp->next=(*current)->next;
            (*current)->next=temp;

            swapped = TRUE;

         }

         /* Go to the next element */
         current = &((*current)->next);

      } /* end while we're going through the list */

   } /* end while not sorted */

} /* end SortTeams() */

void ReadTeams(void) {

   element_t Team;
   element_t *temp;
   int i, temp_int;

   FoundEOF = FALSE;
   
   ReadInt(&(numTeams));
   ReadEOL();

   //printf("numTeams is %d\n", numTeams);

   /* Loop through the file while entries remain */
   for(i=0;i<numTeams;i++) {
   //printf("Reading in team %d\n", i);
      /* Read the next entry */
      ReadString(Team.Name);
      
      /* If we found the EOF, we're done... */
      if (FoundEOF == TRUE) {
         return;
      }

      /* Otherwise, the next entry is there, so read it! */
      ReadComma();
      ReadString(Team.Mascot);
      ReadComma();
      ReadInt(&(temp_int));
      Team.Offense = (int) temp_int;
      ReadComma();
      ReadInt(&(Team.Defense));
      //printf("Reading in EOL\n");
      ReadEOL();
      //printf("Read team done\n");
      /* Now put the entry in the list... */
      temp = TeamList;
      TeamList = NULL;
      TeamList = malloc(sizeof(element_t));
      if (TeamList == NULL) {
         fprintf(stderr,"malloc failed!\n");
         exit(-1);
      }
      *TeamList=Team;
      TeamList->next = temp;

   } /* end for */

}

void ReadEOL() {

   int done = FALSE;
   char c;

   /* Read the End Of Line */
   while (done == FALSE) {
      c = fgetc(infile);
      if (c == '\n') {
         done = TRUE;
      }
      else if (c == EOF) {
         FoundEOF = TRUE;
	 done = TRUE;
      }
   }
}

void ReadInt(int *theinteger) {

   /* Read in an integer */
   fscanf(infile,"%d",theinteger);

   /* Return */
   return;

}

void ReadString(char string[MAX_STRING]) {
   int done = FALSE;
   int index = 0;
   char c;

   /* Read in everything to the next comma as a string */
   while (done == FALSE) {
      c = fgetc(infile);
      if (c == ',' || c == EOF) {
         done = TRUE;
         if (c == EOF) FoundEOF = TRUE;
         if (c == ',') ungetc(c,infile);
         continue;
      }

      string[index++]=c;
   }

   /* Add the terminator and return*/
   string[index]='\0';

   return;

}

void ReadComma() {
   int done=FALSE;
   char c='\0';

   /* Ok, this might be tough... read a single comma! */
   while (done == FALSE) {
      c = fgetc(infile);
      if ( c == ',' ) done=TRUE;
   }

   /* Return */
   return;
}

/** DEBUG **/
void PrintTeams() {

   element_t *looper = TeamList;

   /* Loop through the linked list of teams */

   //fprintf(stdout,"\nHere is the current list:\n");

   while (looper != NULL) {

      /* Print the next team's entry */
      fprintf(stdout,"Team: %s, Mascot: %s, Off: %d, Def: %d\n",
              looper->Name,
              looper->Mascot,
              looper->Offense,
              looper->Defense);

      /* Increment to the next team... */
      looper = looper->next;

   }

   /* Return */
   return;
}

void PrintTeamsArray(void) {

   int index;

   /* Loop through the array of teams */

   fprintf(stdout,"\nHere is the current list:\n");

   for (index=0; index < ArraySize; index++) {

      /* Print the next team's entry */
      fprintf(stdout,"Team: %s, Mascot: %s, Off: %d, Def: %d\n",
              TeamArray[index]->Name,
              TeamArray[index]->Mascot,
              TeamArray[index]->Offense,
              TeamArray[index]->Defense);

   }

   /* Return */
   return;
}

/** DEBUG **/