Results 1 to 6 of 6

Thread: Problem

  1. #1

    Problem

    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.

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

  2. #2
    thinBasic MVPs kryton9's Avatar
    Join Date
    Nov 2006
    Location
    Naples, Florida & Duluth, Georgia
    Age
    67
    Posts
    3,869
    Rep Power
    404

    Re: Problem

    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.
    Acer Notebook: Win 10 Home 64 Bit, Core i7-4702MQ @ 2.2Ghz, 12 GB RAM, nVidia GTX 760M and Intel HD 4600
    Raspberry Pi 3: Raspbian OS use for Home Samba Server and Test HTTP Server

  3. #3
    thinBasic MVPs
    Join Date
    May 2007
    Location
    UK
    Posts
    1,427
    Rep Power
    159

    Re: Problem

    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

    NOT COMPLETE
    Home Desktop : Windows 7 - Intel Pentium (D) - 3.0 Ghz - 2GB - Geforce 6800GS
    Home Laptop : WinXP Pro SP3 - Intel Centrino Duo - 1.73 Ghz - 2 GB - Intel GMA 950
    Home Laptop : Windows 10 - Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz, 2401 Mhz, 2 Core(s), 4 Logical Processor(s) - 4 GB - Intel HD 4400
    Work Desktop : Windows 10 - Intel I7 - 4 Ghz - 8GB - Quadro Fx 370

  4. #4
    thinBasic MVPs
    Join Date
    May 2007
    Location
    UK
    Posts
    1,427
    Rep Power
    159

    Re: Problem

    And here is an answer from google
    http://translate.googleusercontent.c...zS5h8yH_3gMhow

    [code=pascal] &#91;] [Title Solution]
    { (
    ID: Wandsea1 ID: Wandsea1
    PROG: beads PROG: beads
    LANG: PASCAL LANG: PASCAL
    } )
    Program beads; Program beads;
    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
    Assign(input, 'beads.in'); Reset(input); Assign (input, 'beads.in'); Reset (input);
    Assign(output, 'beads.out'); Rewrite(output); Assign (output, 'beads.out'); Rewrite (output);
    readln(n); readln (n);
    for i:=1 to n do for i: = 1 to n do
    begin begin
    read(s[i]); read (s [i]);
    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.[/code]
    Home Desktop : Windows 7 - Intel Pentium (D) - 3.0 Ghz - 2GB - Geforce 6800GS
    Home Laptop : WinXP Pro SP3 - Intel Centrino Duo - 1.73 Ghz - 2 GB - Intel GMA 950
    Home Laptop : Windows 10 - Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz, 2401 Mhz, 2 Core(s), 4 Logical Processor(s) - 4 GB - Intel HD 4400
    Work Desktop : Windows 10 - Intel I7 - 4 Ghz - 8GB - Quadro Fx 370

  5. #5
    thinBasic MVPs kryton9's Avatar
    Join Date
    Nov 2006
    Location
    Naples, Florida & Duluth, Georgia
    Age
    67
    Posts
    3,869
    Rep Power
    404

    Re: Problem

    Now that is a great search to find the solution in the language requested Michael.
    Acer Notebook: Win 10 Home 64 Bit, Core i7-4702MQ @ 2.2Ghz, 12 GB RAM, nVidia GTX 760M and Intel HD 4600
    Raspberry Pi 3: Raspbian OS use for Home Samba Server and Test HTTP Server

  6. #6

    Re: Problem

    thx....:
    i've been doing it for weeks...

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •