PDA

View Full Version : Problem

opel_howard
26-06-2010, 18:48
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
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.

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
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

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

SAMPLE OUTPUT
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

i'm confused...could somebody help me???

kryton9
26-06-2010, 22:20
Scan through the line and break it into segments with counts(| will be segment breaks):

count: 1 1 1 3 3 4 1 2 2 1 4 4 1
segment: 1 2 3 4 5 6 7 8 9 10 11 12 13
b|r|b|rrr|bbb|rrrrr|b|rr|bb|r|bbbb|rrrr|b

now scan through counts with 2 neighbors with the largest counts.
in this case segment 11 and 12

I don't have free pascal installed at the moment to write the code for you.
Let me know if you need more help. Hopefully this will get you on your way.

Michael Clease
26-06-2010, 23:06
This looks a lot like homework from school /college and unless the OP quotes any help given it might be seen as unfair to help.

Kents answer if all you need.

There are lots of ways to do this but you could with simple loops.
Psuedo code

mystring = "bbrrrrbbbrrbbbr"
Myarray1(Len(MyString))
Myarray2(Len(MyString))
counter = 1
Offset = 0
Element = 1
Do
DO
if mids(check,Offset+counter,1) = mids(check,Offset+counter+1,1) THEN INCR Counter
Loop While Offset+Counter < Len(mystring)
MyArray1(mids(check,Offset,1),Element)
MyArray2(Element)
Offset += Counter
INCR Element
Loop While Offset+Counter < Len(mystring)
For n = 1 TO UBOUND(MyArray)-1
IF MyArray2(n) > MyArray2(n+1) THEN Breakpoint1 = n
Next
For n = UBOUND(MyArray)-1 TO 1 STEP -1
IF MyArray2(n) > MyArray2(n-1) Then Breakpoint2 = n
Next

:diablo: NOT COMPLETE

Michael Clease
26-06-2010, 23:48

&#91;] [Title Solution]
{ (
ID: Wandsea1 ID: Wandsea1
LANG: PASCAL LANG: PASCAL
} )
Var Var
n,l,i:integer; n, l, i: integer;
s:array [0..801] of char; s: array [0 .. 801] of char;
lr,lb,rr,rb:array[0..701] of integer; lr, lb, rr, rb: array [0 .. 701] of integer;

function max(a,b:integer):integer; function max (a, b: integer): integer;
begin begin
if a>b then max:=a else max:=b; if a> b then max: = a else max: = b;
end; end;

function min(a,b:integer):integer; function min (a, b: integer): integer;
begin begin
if a<b then min:=a else min:=b; if a <b then min: = a else min: = b;
end; end;

Begin Begin
for i:=1 to n do for i: = 1 to n do
begin begin
s[n+i]:=s[i]; s [n + i]: = s [i];
end; end;

lb[0]:=0; lb [0]: = 0;
lr[0]:=0; lr [0]: = 0;
for i:=1 to 2*n-1 do for i: = 1 to 2 * n-1 do
begin begin
if s[i]='w' then if s [i] = 'w' then
begin begin
lb[i]:=lb[i-1]+1; lb [i]: = lb [i-1] +1;
lr[i]:=lr[i-1]+1; lr [i]: = lr [i-1] +1;
end; end;
if s[i]='r' then if s [i] = 'r' then
begin begin
lb[i]:=0; lb [i]: = 0;
lr[i]:=lr[i-1]+1; lr [i]: = lr [i-1] +1;
end; end;
if s[i]='b' then if s [i] = 'b' then
begin begin
lb[i]:=lb[i-1]+1; lb [i]: = lb [i-1] +1;
lr[i]:=0; lr [i]: = 0;
end; end;
end; end;

rr[2*n-1]:=0; rr [2 * n-1]: = 0;
rb[2*n-1]:=0; rb [2 * n-1]: = 0;
for i:=(2*n-2) downto 0 do for i: = (2 * n-2) downto 0 do
begin begin
if s[i+1]='w' then if s [i +1] = 'w' then
begin begin
rr[i]:=rr[i+1]+1; rr [i]: = rr [i +1] +1;
rb[i]:=rb[i+1]+1; rb [i]: = rb [i +1] +1;
end; end;
if s[i+1]='r' then if s [i +1] = 'r' then
begin begin
rr[i]:=rr[i+1]+1; rr [i]: = rr [i +1] +1;
rb[i]:=0; rb [i]: = 0;
end; end;
if s[i+1]='b' then if s [i +1] = 'b' then
begin begin
rb[i]:=rb[i+1]+1; rb [i]: = rb [i +1] +1;
rr[i]:=0; rr [i]: = 0;
end; end;
end; end;

l:=0; l: = 0;
for i:=0 to (2*n-1) do for i: = 0 to (2 * n-1) do
l:=max(l,max(lr[i],lb[i])+max(rr[i],rb[i])); l: = max (l, max (lr [i], lb [i]) + max (rr [i], rb [i]));
l:=min(l,n); l: = min (l, n);
writeln(l); writeln (l);

Close(input);Close(output); Close (input); Close (output);
End. End.

kryton9
27-06-2010, 00:58
Now that is a great search to find the solution in the language requested Michael.

opel_howard
29-06-2010, 17:30
thx....: :o
i've been doing it for weeks...