DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Roger has posted 34 posts at DZone. View Full User Profile

USACO Barn Repair Problem

01.23.2009
| 1366 views |
  • submit to reddit
        // Solution for USACO's barn1 problem, with some extra debugging output thrown in

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

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 <lastCow; x++) {
        boardArray[x] = 1;
    }
    
    gap thisGap, longGap;
    memset(&thisGap, 0, sizeof thisGap);
    memset(&longGap, 0, sizeof longGap);
    /* then for each board find the biggest gap you can create*/
    printStallArrays(stalls, stallArray, boardArray);
    for (x=0; x < boards-1; x++) {
        for (y=firstCow; y <=lastCow; ++y) {
            if (stallArray[y] == 0 && boardArray[y] == 1) {
                if (inGap) {
                    thisGap.length++;
                } else {
                    inGap = true;
                    thisGap.begin = y;
                    thisGap.length++;
                }  
            } else if (inGap){
                inGap = false;
                if (thisGap.length > 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;
}