C++ · problem solving

USACO 1.1.4 Broken Necklace

You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random.

When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration can include any of the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.

SAMPLE INPUT (file beads.in)

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

OUTPUT FORMAT

A single line containing the maximum of number of beads that can be collected from the supplied necklace.

SAMPLE OUTPUT (file beads.out)

11

OUTPUT EXPLANATION

Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.

                Two necklace copies joined here
                             v
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb|wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
                       ******|*****
                       rrrrrb|bbbbb  <-- assignments
                   5xr .....#|#####  6xb

                        5+6 = 11 total

Solution:

/*
ID: ahmedye1
PROG: beads
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

ifstream ifile("beads.in");
ofstream ofile("beads.out");
int n;
string breads;
int flag = 0;
char tempChar;

string convert(string breads)
{
    for (int i = 0; i < breads.length(); i++)
    {
       if (breads[i] == 'w')
       {
          tempChar = 'w';
          if (i == 0)
          {
            for (int j = i+1; j < breads.length(); j++)
            {
              if (breads[j] == 'r')
              {
                 breads[i] = 'r';
                 break;
              }
              else if (breads[j] == 'b')
              {
                breads[i] = 'b';
                break;
              }
            }         
         }
         else if (breads[i - 1] == breads[i + 1])
                  breads[i] = breads[i - 1];
     else
     {
       int rightCounter = 0;
       int leftCounter = 1;
       int temp = 0;
       int flag = 0;
 
       for (int j = i+1; j < breads.length(); j++)
       {
           if (breads[i-1] == breads[j] || j == breads.length()-1) 
           {
              for (int k = i; k < j; k++) 
              {
                if (breads[k] != 'w')
                {
                  tempChar = breads[k]; 
                  flag = 1;
                  break;
                }
              }
            if (flag == 1)
               break;
           }
           else
           {
              if (tempChar != 'r' || tempChar != 'b')
              tempChar = breads[i - 1];
              rightCounter++;
 
              if (breads[j] == 'w')
              temp++;
           }
       }
      rightCounter -= temp;
 
    for (int j = i-1; j >= 0; j--)
    {
       if (j-1 != -1)
       {
          if (breads[j] == breads[j - 1])
              leftCounter++;
          else
             break;
       }
     }
     if (rightCounter > leftCounter)
         breads[i] = tempChar;
     else if (rightCounter == leftCounter)
         breads[i] = 'b';
     else 
         breads[i] = breads[i - 1];
    }
  }
 }
 return breads;
}
int main()
{
  int counter = 1;
  int maxCounter = 0;

  ifile >> n;
  ifile >> breads;
  breads = convert(breads);
  breads += breads;

  for (int i = 0; i < breads.length(); i++)
  {
    for (int j = i + 1; j < breads.length(); j++)
    {
      if (breads[i] == breads[j])
      counter++;
      else if (breads[i] != breads[j])
      {
        if (breads[j] == breads[j + 1])
        counter++;
        else
        {
          counter++;
          break;
        }
      }
    }
   if (maxCounter <= counter)
       maxCounter = counter;
   if (maxCounter >= n)
       maxCounter = n;
   counter = 1;
 }
ofile << maxCounter << endl;
 return 0;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s