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**:

**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