Founds

Minimum Scalar Product

My solution for the Minimum Scalar Product problem of Round 1A of Google Code Jam 2008:


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


int cmpA(const void *v1, const void *v2) {
  int *e1 = (int*)v1, *e2 = (int*)v2;
  if (*e1 < *e2) return 1;
  if (*e1 > *e2) return -1;
  return 0;
}
int cmpB(const void *v1, const void *v2) {
  int *e1 = (int*)v1, *e2 = (int*)v2;
  if (*e1 < *e2) return -1;
  if (*e1 > *e2) return 1;
  return 0;
}


main() {
  char str[4096];
  int N, n, Q;
  int iN, i;
  long long result;

  int A[800], B[800];
  int rA[800], rB[800];
  int sA, sB;
  int pA, pB;
  int zA, zB;
 
  fgets(str, sizeof(str), stdin);
  sscanf(str, "%d", &N);
  fprintf(stderr, "N:%d\n", N);

  for (iN = 0; iN < N; iN++) {

    result = 0;

    fscanf(stdin, "%d", &n);
    fprintf(stderr, "Case#%d N:%d\n", (iN+1), n);
    
 
    for(i = 0; i < n; i++) {
      fscanf(stdin, "%d", &A[i]);
    }
    for(i = 0; i < n; i++) {
      fscanf(stdin, "%d", &B[i]);
    }
    qsort(A, (size_t)n, sizeof(*A), &cmpA);
    qsort(B, (size_t)n, sizeof(*B), &cmpB);
 
    for(i = 0; i < n; i++) {
      result += (long long)A[i] * (long long)B[i];
    }

    fprintf(stdout, "Case #%d: %lld\n", iN + 1, result);

  }
  return 0;
}