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