# Google codejam Qualification Round Africa and Arabia 2011 Problem A. Closing the Loop

23 Jul

### Problem

Given a bag full of rope segments, you will build the longest loop of rope while alternating colors. The bag contains S segments and each segment will either be blue (B) or red (R). You are required to alternate between colors and because of this requirement you might not use every segment in the bag. If you only have segments of a single color, you will not be able to tie any knots and should output `0`. Each segment length is provided in centimeters and each knot in the loop consumes one centimeter of length from the loop. In other words, a knot consumes one-half of a centimeter from of the two segment it connects.

Note that pieces of string that have length 1, if used in making the cycle, might get reduced to just a pair of knots of total length 0. This is allowed, and each such piece counts as having been used.

### Input

The first line of input gives the number of cases, N.
N test cases follow. For each test case there will be:

• One line containing the value S, the number of rope segments in the bag.
• One line containing a space separated list of S values. Each value L indicates the segment length in centimeters followed by the letter B or R to indicate the segment color.

### Output

For each test case, output one line containing “Case #x: ” followed by the maximum length of the rope loop that can be generated with the rope segments provided.

### Limits

1 ≤ number of rope segments (S) ≤ 1000
1 ≤ length of a rope segment (L) ≤ 100

N ≤ 5

N ≤ 50

### Sample

 Input Output ``` 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```

### Solution

```from sys import stdin

f = open('output.out', 'w')

blue = []
red = []

for j in segments:
if j[len(j)-1] == 'B':
blue.append(int(j[0:len(j)-1]))
else:
red.append(int(j[0:len(j)-1]))

if len(blue) == 0 or len(red) == 0:
print 'Case #'+str(i+1)+': 0'
f.write('Case #'+str(i+1)+': 0\n')
continue

blue = sorted(blue, reverse = True)
red = sorted(red, reverse = True)

sum = 0
segUsed = 0

length = 0
if len(blue) > len(red):
length = len(red)
else :
length = len(blue)

for k in range(0, length):
sum += blue[k]
sum += red[k]
segUsed += 2

print 'Case #'+str(i+1)+': ' + str(sum-segUsed)
f.write('Case #'+str(i+1)+': ' + str(sum-segUsed)+'\n')

f.close()

```

### One Response to “Google codejam Qualification Round Africa and Arabia 2011 Problem A. Closing the Loop”

1. guild wars 2 gold August 20, 2012 at 3:26 pm #

I have been absent for a while, but now I remember why I used to love this web site. Thank you, I will try and check back more often. How frequently you update your web site?