Programozás‎ > ‎Feladatok‎ > ‎

Elszakadt nyaklánc

Van egy nyakláncunk, ami N gyöngyből áll, ezek fehérek, pirosak vagy kékek (3<=N<=350), véletlenszerű elrendezésben.

Itt látható két példa N = 29-re:. 
   
            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
            
                        r piros gyöngy

                        b kék gyöngy

                        w fehér gyöngy

Az első és második gyöngy az ábrán meg lett jelölve. Az első ábrán lévő nyaklánc csak kék és piros gyöngyökből áll, és leírható a következő 'b'-kből és 'r'-ekből álló karakterlánccal (ha a 3. gyöngynél kezdjük a leírást): 

    brbrrrbbbrrrrrbrrbbrbbbbrrrrb

A nyaklánc egy helyen elszakítható és kiteríthető egyenesen. Ezután mindkét végéről levehetők gyöngyök a következő módon: elindulunk a lánc végén, és addig szedjük le a gyöngyöket, amíg az elsővel azonos színűek. Ezt ismételjük a másik végén is, de ezek a gyöngyök eltérhetnek színben az előbb leszedettektől (egymástól viszont nem).

Feladat

Írjunk programot, ami megadja, hol kell elszakítani a nyakláncot ahhoz, hogy a lehető legtöbb gyöngyöt tudjuk összeszedni.

A fenti első ábrán például 8 gyöngy gyűjthető össze, ha a 9. és 910., vagy ha a 24. és 25. gyöngy között szakítunk.

Vannak olyan nyakláncok is, amelyekben fehér gyöngyök is találhatók, m int például a fenti második ábrán. A gyöngyök gyűjtésekor ezek tekinthetők pirosnak és kéknek is. Az ilyen nyakláncok leírása az előzőhöz hasonló, de 'w' karakterek is szerepelhetnek benne, melyek a fehér gyöngyök helyét jelölik. 

Bemenet

A bemenet első sora a gyöngyök N számát adja meg, a másodikban pedig N karakter található, a gyöngyök színe.

Kimenet

A begyűjthető gyöngyök maximális száma.

Példa

Bemenet  Kimenet
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
 11

A példa magyarázata:
Képzeljül el, hogy kétszer egymás után illesztettük a nyakláncot (mintha a végén tovább lehetne haladni körben). 

                A nyaklánc két azonos példánya itt van összeillesztve
                             v
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb|wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
                       ******|*****
                       rrrrrb bbbbb  <-- a fehérek választása
                       rrrrr#bbbbbb  
                       5 x r  6 x b  <-- összesen 11

Tesztadatok

Címkék

A feladat forrása: USACO training material, Broken Necklace
Algoritmusok: 

megoldás