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 Beads In C++

11.04.2008
| 1987 views |
  • submit to reddit
        // Here's my solution to the USACO Beads algorithm problem. In C++, 
// using a circularly linked list

#include <iostream>
#include <fstream>

using namespace std;

struct bead {
   char color;
   bead* next;
   bead* previous;
   bool breakflag;
   bool firstbreak;
};

bead* addBead(bead *node, char color) {
    bead *newNode = (bead *)malloc(sizeof(bead));
    if (newNode == NULL) {
        return NULL;
    }
    newNode->color = color;
    newNode->breakflag = false;
    newNode->firstbreak = false;
    newNode->next = node->next;
    newNode->previous = node;
    node->next = newNode;
    return newNode;
}


bead* getNextColor(bead* current, bool goLeft, char curcolor) {
    bead* node = current;
    do {   
        if (goLeft) {
            node = node->previous;
        } else {
            node = node->next;
        }
        if ((node->color != 'w') && (node->color != curcolor)) {
            return node;
        }
    } while (node != current);
    return NULL;
}

bead* searchForBreak(bead* current, bool goLeft, char curcolor) {
    bead* node = current;
    while ((current->color == curcolor) || (current->color == 'w')) {
        if (goLeft) {
            current = current->previous;
        } else {
            current = current->next;
        }
        if (node == current) return NULL;
    }
    current->next->breakflag = true;
    return current->next;
}

int countFromBreak(bead* current, bool goLeft, char curcolor) {
    int count = 0;
    while ((current->color == curcolor) || current->color == 'w') {
        if (goLeft) {
            current = current->previous;
        } else {
            current = current->next;
        }
        ++count;
    }
    return count;
}

int main() {
   ofstream fout ("beads.out");
   ifstream fin ("beads.in");

   int numbeads;
   fin >> numbeads;
   char beads[numbeads];
   bead* current;
   fin >> beads;

   current = NULL;
   
   bead* first = (bead*)malloc(sizeof(bead));
   first->color = beads[0];
   first->next = NULL;
   first->breakflag = false;
   current = first;
   for (int x = 1; x < numbeads; x++) {
       current = addBead(current, beads[x]);
   }
   current->next = first;
   first->previous = current;
   current = first;
   
   char curcolor = current->color;
   
   if (curcolor == 'w') {
       current = getNextColor(current, true, 'w');     
       if (current == NULL) {
           fout << numbeads << endl;
           return 0;
       } else curcolor = current->color;
   } 
   current = searchForBreak(current, true, curcolor);
   if (current == NULL) {
       fout << numbeads << endl;
       return 0;
   }
   current->firstbreak = true;
   current->breakflag = true;
   
   int maxsize = 0;
   int newsize = 0;
 
   do {
       newsize = countFromBreak(current, false, curcolor);
       curcolor = (curcolor == 'b') ? 'r' : 'b';
       newsize += countFromBreak(current->previous, true, curcolor);
       if (newsize > numbeads) newsize = numbeads;
       if (newsize > maxsize) maxsize = newsize;
       current = searchForBreak(current->previous, true, curcolor);
   } while (!current->firstbreak);

   fout << maxsize << endl;

   return 0;
}