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;
}
Below is python code for the same problem
f=open("round1A-large.in")
def integer():
s=f.readline()
s=s.strip()
s=int(s)
return s
def string():
s=f.readline()
s=s.strip();
return s
def array():
s=f.readline()
s=s.strip()
s=s.split()
for i in range(len(s)):
s[i]=int(s[i])
return s
noTests=integer()
for i in range(noTests):
integer()
row1=array()
row2=array()
row1.sort()
row2.sort()
row2.reverse()
Sum=0
for ii in range(len(row1)):
Sum += row1[ii]*row2[ii]
print "Case #%d: %d" %(i+1,Sum)