USACO FEB08 Problem 'racing' Analysis

by Rob Kolstad

This problem uses a straightforward, almost greed, algorithm to determine the furthest Bessie can run from her starting point. The insight is to notice that any path she runs one way will be run again when she returns. Thus, we must only count through paths until we are "too far" and then report an answer that is just a bit less than "too far".

My solution is pretty simple -- it reads through the data and calculates how long it takes to traverse a segment both ways. When that segment's time causes the total to go over the limit, then the proper number of segments is reported.

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

main () {
    FILE *fin = fopen ("racing.in", "r");
    FILE *fout = fopen ("racing.out", "w");
    int m, t, u, f, d, thistime, totaltime, i;
    char line[80];
    fscanf (fin, "%d %d %d %d %d", &m, &t, &u, &f, &d);
    totaltime = 0;
    for (i = 0; i < t; i++) {
        fscanf (fin, "%s", line);
        if (line[0] == 'u' || line[0] == 'd') thistime = u+d;
        if (line[0] == 'f') thistime = f+f;
        if (totaltime + thistime > m) {
            fprintf (fout, "%d\n", i);
            exit (0);
        }
        totaltime += thistime;
    }
    fprintf (fout, "%d\n", i);
    exit (0);
}

The code of Contest Director Christos is even shorter and uses compact coding to achieve the same results:

#include<cstdio>

int M, T, U, F, D, A;

int main() {
    char c;
    FILE *fin = fopen("racing.in", "r");
    FILE *fout = fopen("racing.out", "w");
    fscanf(fin,"%d %d %d %d %d",&M, &T, &U, &F, &D);
    for(A=0;A<T;A++) {
        fscanf(fin," %c ",&c);
        if(c=='f') M-=2*F;
        else M-=U+D;
        if(M<0) break;
    }
    fprintf(fout,"%d\n",A);
    return 0;
}