Train Timetable

Rate this post

My solution for the Train Timetable task of Google Code Jam 2008 qualification round:


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

typedef struct {
  int d[24*60];
  int a[24*60];
} STATION;

main () {
  char str[4096];
  STATION A, B;

  int N, T, NA, NB;
  int i, iN;
  int dh, dm, ah, am;
  int resultA, resultB;

  fgets(str, sizeof(str), stdin);
  sscanf(str, "%d", &N);
 
  for (iN = 0; iN < N; iN++) {
    bzero(&A, sizeof(A));
    bzero(&B, sizeof(B));
    resultA = resultB = 0;

    fgets(str, sizeof(str), stdin);
    sscanf(str, "%d", &T);

    fgets(str, sizeof(str), stdin);
    sscanf(str, "%d %d", &NA, &NB);
 
    for(i = 0; i < NA; i++) {
      fgets(str, sizeof(str), stdin);
      sscanf(str, "%02d:%02d %02d:%02d", &dh, &dm, &ah, &am);
      A.d[60*dh+dm]++;
      am += T;
      if (am > 59) { 
	ah++; am -= 60;
      } 
      if (ah < 24) B.a[60*ah+am]++; 
     }
    for(i = 0; i < NB; i++) {
      fgets(str, sizeof(str), stdin);
      sscanf(str, "%02d:%02d %02d:%02d", &dh, &dm, &ah, &am);
      B.d[60*dh+dm]++;
      am += T;
      if (am > 59) { 
	ah++; am -= 60; 
      }
      if (ah < 24) A.a[60*ah+am]++; 
    }

    NA = NB = 0;
    
    for (dh = 0; dh < 24; dh++) {
      for (dm = 0; dm < 60; dm++) {
	NA += A.a[60*dh+dm];
	if (NA < A.d[60*dh+dm]) {
	  resultA += (A.d[60*dh+dm] - NA);
	  NA = 0;
	} else NA -= A.d[60*dh+dm];
 
	NB += B.a[60*dh+dm];
	if (NB < B.d[60*dh+dm]) {
	  resultB += (B.d[60*dh+dm] - NB);
	  NB = 0;
	} else NB -= B.d[60*dh+dm];
    }
    }
    fprintf(stdout, "Case #%d: %d %d\n", (iN+1), resultA, resultB);
  }
  return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *