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

Small dataset

N ≤ 5

Large dataset

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')
for i in range(0, int(stdin.readline())):
stdin.readline()
segments = stdin.readline().split()

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()

Input

change extension to .txt
Advertisements

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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: