NézetNyomtat

Csomózás
Címkék > Feladat

Csomózás

Van egy ládánk, amiben piros (R=red) és kék (B=blue) kötéldarabok vannak. Szeretnénk ezekből a lehető leghosszabb kört előállítani úgy, hogy váltakozva piros és kék köteleket csomózunk össze. Persze előfordulhat, hogy a váltakozás miatt nem tudjuk az összes kötelet felhasználni. Tudjuk, hogy két kötéldarab összecsomózásához 1 centiméternyi kötelet kell felhasználni, ezt tekinthetjük úgy, hogy mindkét darab végén egy fél centis részt használunk a csomóhoz. Az is megengedett, hogy egy 1 centis kötelet használjunk: ekkor ugyan teljes hossza a csomóba kerül, de biztosíthatja a színek váltakozását.

Feladat

Írjunk programot, ami megadja az elkészíthető leghosszabb váltakozó színű kör hosszát.

Bemenet

Az első sor a tesztesetek számát tartalmazza. Minden tesztesethez két sor tartozik: a ládában lévő kötéldarabok száma, majd a darabok leírása, szóközzel elválasztva. Egy kötél leírása egy számjeggyel kezdődő karakterlánc, ami először a kötél hosszát adja meg (centiméterben), majd a kötél színének kezdőbetűjével zárul. Legfeljebb 1000 kötél van, és legfeljebb 100 egy kötéldarab hossza.

Kimenet

Tesztesetenként egy sor: a leghosszabb elkészíthető kör hossza.

Példa

Bemenet Kimenet
4
1
5B
4
6R 1B 7R 3B
7
5B 4R 3R 2R 5R 4R 3R
2
20B 20R
Case #1: 0
Case #2: 13
Case #3: 8
Case #4: 38

Tesztadatok