USACO OCT08 qual Problem 'bones' Analysis

by David Benjamin

The number of distinct die rolls is S1*S2*S3 <= 20*20*40 = 16000, so we can afford to simply loop over them all, maintaining a count of how often each sum occurs. From this we can determine the most common sum.

#include <assert.h>
#include <stdio.h>

const int MAXS1 = 20 + 5;
const int MAXS2 = 20 + 5;
const int MAXS3 = 40 + 5;
int count[MAXS1 + MAXS2 + MAXS3 + 1];

int main() {
    FILE * fin = fopen("bones.in", "r");
    FILE * fout = fopen("bones.out", "w");
    assert(fin != NULL); assert(fout != NULL);

    int s1,s2,s3;
    fscanf(fin, "%d %d %d", &s1, &s2, &s3);
    
    /* count possible rolls */
    for (int i=1;i<=s1;i++)
        for (int j=1;j<=s2;j++)
            for (int k=1;k<=s3;k++)
                count[i+j+k]++;

    /* find the best */
    int best = 0;
    for (int i=3;i<=s1+s2+s3;i++)
        if (count[i] > count[best])
            best = i;

    fprintf(fout, "%d\n", best);

    return 0;
}