I am trying to solve the USACO problem beads. In this problem, you are given a string of beads, and you have to find the maximum consecutive pair of red and blue beads.
Example: IF you were given the string wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb
, the maximum length would be 11 as you would split the string at these two intervals wrwrrbwwwbb
The w
counts as both a red or blue bead, depending on what is favorable to you.
My solution is to have a count where I sort of split up each of the sections into different colors and then progressively add them and get the overall max.
Ex: IF we were using the string "rrbbwwrrb", my possible list of counts would be [6,5] My different sections would be rrbbww, bbwwrr, and wwrrb.
Logically this seems like the correct solution, but it is the coding part of it that is stumping me. Here is my code:
neck = "wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb"
n = len(neck)
maxi = -1 #max length
c = 0 #counter
changes = 1 #number of color swaps
curr = 0 #each part
color = None
for i in range(n):
if neck[i] == 'w':
c += 1
if changes == 2:
curr += 1
elif neck[i] == color:
c += 1
if changes == 2:
curr += 1
else:
if changes == 3:
color = neck[i]
maxi = max(c,maxi)
#print(str(c) + str(" ") + str(i))
c = 1
curr = 1
changes = 1
else:
color = neck[i]
c += 1
if changes == 2:
curr += 1
changes += 1
print(maxi)
The correct answer is 11, but my coded solution reports 9.
Aucun commentaire:
Enregistrer un commentaire