Over a million developers have joined DZone.

USACO Barn Repair Problem

·
// Solution for USACO's barn1 problem, with some extra debugging output thrown in


#include 
#include 
#include 
#include 

typedef struct gap gap;

struct gap {
    int begin;
    int length;
};

int compare (const void * a, const void * b) {
    return ( *(int*)a - *(int*)b );
}

int printStallArrays(int stalls, int stallArray[stalls], int boardArray[stalls]) {
    int x;
    printf("stallArray: ");
    for (x = 0; x < stalls; ++x) {
        printf("%d", stallArray[x]);
    }
    printf("\n");
    
    printf("boardArray: ");
    for (x = 0; x < stalls; ++x) {
        printf("%d", boardArray[x]);
    }
    printf("\n\n");
    
    return EXIT_SUCCESS;
}

int main(void) {
    FILE *fin, *fout;
    fin = fopen("barn1.in", "r");
    fout = fopen("barn1.out", "w");
    int boards, stalls, cows;
    int x, y;
    int firstCow, lastCow;
    int numCovered = 0;
    bool inGap = false;
    
    fscanf(fin, "%d %d %d", &boards, &stalls, &cows);
    int stallArray[stalls];
    memset(stallArray, 0, sizeof stallArray);
    int boardArray[stalls];
    memset(boardArray, 0, sizeof boardArray);
    int cowArray[cows];
    memset(cowArray, 0, sizeof cowArray);
    for (x=0; x < cows; x++) {
        fscanf(fin, "%d", &cowArray[x]);
    }
    qsort(cowArray, cows, sizeof(int), compare);
    for (x=0; x < cows; x++) {  
        stallArray[cowArray[x]-1] = 1;
        boardArray[cowArray[x]-1] = 1;
        if (x == 0) {
            firstCow = cowArray[x]-1;
        }
    }
    lastCow = cowArray[x-1] - 1;
    
    /* cover all the cows with board 1 */
    for (x=firstCow; x  longGap.length) {
                    longGap.begin = thisGap.begin;
                    longGap.length = thisGap.length;
                }
                memset(&thisGap, 0, sizeof thisGap);
            }
        }
        
        int j;
        for (j = longGap.begin; j < longGap.begin + longGap.length; j++) {
            boardArray[j] = 0;
        }
        memset(&longGap, 0, sizeof longGap);
        memset(&thisGap, 0, sizeof thisGap);
        printStallArrays(stalls, stallArray, boardArray);
    }
    
    for (x=0; x < stalls; x++) {
        if (boardArray[x] == 1) {
            ++numCovered;
        }
    }

    fprintf(fout, "%d\n", numCovered);
    
	return EXIT_SUCCESS;
}

Topics:

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}