C++

Forum

 
Help...Me...!

regiice9 (21)
Hello. I was working on this problem, and I need help debugging it. the problem is:
"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. Here are two examples for n=29:

1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead
The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).

Determine the point where the necklace should be broken so that the most number of beads can be collected.

Example

For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.

In some necklaces, white beads had been included as shown in Figure B above. 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 will include 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.

PROGRAM NAME: beads

INPUT FORMAT

Line 1: N, the number of beads
Line 2: a string of N characters, each of which is r, b, or w
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.
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** *****
rrrrrb bbbbb <-- assignments
5 x r 6 x b <-- 11 total"
regiice9 (21)
sorry, i had too many characters, but my code is:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
 
#include <fstream>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    ifstream fin("beads.in");
    ofstream fout("beads.out");
    int numbeads, tempblue=0, tempred=0, total=0, b=0, r=0, redcounter=20, bluecounter=20;
    char lastcolor;
    fin>>numbeads;
    vector<int> red(numbeads);
    vector<int> blue(numbeads);
    vector<char> beadcolors(numbeads);
    
    //f-ins the color values
    for(int j=0;j<numbeads;j++)
    {
        fin>>beadcolors[j];
    }
    
    //calculates number of beads
    for(int j=0;j<numbeads;j++)
    {
        if(j>=0&&j<55)
            {
            cout<<"j is "<<j<<"\n";
                cout<<"redcounter is "<<redcounter<<"\n";
            }
        
        //if bead is blue
        if(beadcolors[j]=='b')
        {
            
            if(beadcolors[j-1]=='r'||(beadcolors[j-1]=='w'&&redcounter==0)||j==0)
            {
                if(j==0)
                {
                    lastcolor='r';
                    tempblue=0;
                    blue[0]=0;
                    red[0]=0;
                    tempred=0;
                }
                redcounter=0;
                bluecounter=0;
                tempblue=red[r-1];
            }
            blue[b]++;
            redcounter++;
            if(beadcolors[j+1]=='r'||(j+1)==numbeads)
            {
                tempblue+=blue[b];
                if((j+1)==numbeads)
                {
                    if((beadcolors[0]=='b'||beadcolors[0]=='w')&&r!=0)
                    {
                cout<<"HELLOOOOOOOOOO!";
                        tempblue+=blue[0];
                    }
                }
                if(tempblue>total)
                {
                    total=tempblue;
                }
                b++;
                bluecounter=0;
                lastcolor='b';
                tempred=0;
                red[r]=0;
                
            }
        }
        
        //if bead is red
        if(beadcolors[j]=='r')
        {
            if(beadcolors[j-1]=='b'||(beadcolors[j-1]=='w'&&bluecounter==0)||j==0)
            {
                tempred=blue[b-1];
                red[r]=0;
                bluecounter=0;
                if(j==0)
                {
                    lastcolor='b';
                    tempblue=0;
                    blue[0]=0;
                    red[0]=0;
                    tempred=0;
                }
            }
            red[r]++;
            bluecounter++;
            if(beadcolors[j+1]=='b'||(j+1)==numbeads)
            {
                redcounter=0;
                tempred+=red[r];
                if((j+1)==numbeads)
                {
                    if((beadcolors[0]=='r'||beadcolors[0]=='w')&&b!=0)
                    {
                        tempred+=red[0];
                    }
                }
                if(tempred>total)
                {
                    total=tempred;
                }
                r++;
                tempblue=0;
                blue[b]=0;
                lastcolor='r';
            }
        }
        
        //if bead is white
        if(beadcolors[j]=='w')
        {
            blue[b]++;
            red[r]++;
            
            if(lastcolor=='b'&&beadcolors[j+1]=='b')
            {
                redcounter=0;
                tempred+=red[r];
                if((j+1)==numbeads)
                {
                    if((beadcolors[0]=='r'||beadcolors[0]=='w')&&b!=0)
                    {
                        tempred+=red[0];
                    }
                }
                if(tempred>total)
                {
                    total=tempred;
                }
                r++;
                red[r]=0;
                tempblue=0;
                lastcolor='r';
            }
            if(lastcolor=='r'&&beadcolors[j+1]=='r')
            {
                bluecounter=0;
                tempblue+=blue[b];
                if((j+1)==numbeads)
                {
                    if((beadcolors[0]=='b'||beadcolors[0]=='w')&&r!=0)
                    {
                        tempblue+=blue[0];
                    }
                }
                if(tempblue>total)
                {
                    total=tempblue;
                }
                b++;
                blue[b]=0;
                tempred=0;
                lastcolor='b';
            }
            if(lastcolor=='r'&&beadcolors[j-1]!='r')
            {
                cout<<"HIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII";
                cout<<"j-1=="<<beadcolors[j-1];
                redcounter++;
            }
            if(lastcolor=='b'&&beadcolors[j-1]!='b')
            {
                bluecounter++;
            }
        }
            if(j>=0&&j<55)
            {
            cout<<"tempblue is "<<tempblue<<"\n";
            cout<<"tempred is "<<tempred<<"\n";
            cout<<"blue is "<<blue[b]<<"\n";
            cout<<"red is "<<red[r]<<"\n";
            cout<<"redcounter is "<<redcounter<<"\n";
            cout<<"bluecounter is "<<bluecounter<<"\n";
            cout<<"lastcolor is "<<lastcolor<<"\n";
            cout<<"total is "<<total<<"\n\n";
            }
    }
    fout<<total<<"\n";
    
    /*
    use if to add 1 to temp(color) and also erases other color value
    if j+1 is other color, and temp(color) is greater than (color), then (color) is = 
    to temp(color)
    take total of past group, and add it to temptotal, and then at the end, take 
    current value and add to temp total, and if it is the highest, then it is 
    the total. For the first group, put their total in a different variable,
    and then if the last grouping is the same color, then it is added to their
    subtotal
    (color)counter counts how many runs have passed since end of (color)
    [PROBLEM:in one run, last color needs to be done after the condition for the function, but in the other
    the blue counter can not start until last color is activated]
    [Solution:]
    adds both colors together and fouts the total
    */
    system ("PAUSE");
    return 0;
}

The problem is that I have 2 inputs, and whenever I fix one, the other breaks/has problems. I have been trying for the past 4 days with no luck.
the inputs are:

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
ans:11

77 rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr
ans:74

I explained my code in the comments at the end. let me know of any Q's
Topic archived. No new replies allowed.