Return to problem list2017-1B Problem B
Final solution
func start() {
var t int
mustReadLineOfInts(&t)
for i := 0; i < t; i++ {
fmt.Fprintf(stdout, "Case #%d: ", i+1)
ls := test()
if ls == nil {
stdout.WriteString("IMPOSSIBLE\n")
} else {
stdout.Write(ls)
stdout.WriteByte('\n')
}
}
}
func test() []byte {
var N, R, O, Y, G, B, V int
mustReadLineOfInts(&N, &R, &O, &Y, &G, &B, &V)
preList := make([][]byte, 0, 3)
nR := R
nY := Y
nB := B
if O > 0 {
if B == O && N == O*2 {
rep := make([]byte, N)
for i := 0; i < N; i += 2 {
rep[i] = 'B'
rep[i+1] = 'O'
}
return rep
}
if B < O+1 {
return nil
}
B -= O + 1
ll := make([]byte, O*2+1)
ll[0] = 'B'
for i := 1; i < len(ll); i += 2 {
ll[i] = 'O'
}
for i := 2; i < len(ll); i += 2 {
ll[i] = 'B'
}
O = 0
preList = append(preList, ll)
nB = B + 1
}
if G > 0 {
if R == G && N == G*2 {
rep := make([]byte, N)
for i := 0; i < N; i += 2 {
rep[i] = 'R'
rep[i+1] = 'G'
}
return rep
}
if R < G+1 {
return nil
}
R -= G + 1
ll := make([]byte, G*2+1)
ll[0] = 'R'
for i := 1; i < len(ll); i += 2 {
ll[i] = 'G'
}
for i := 2; i < len(ll); i += 2 {
ll[i] = 'R'
}
G = 0
preList = append(preList, ll)
nR = R + 1
}
if V > 0 {
if Y == V && N == V*2 {
rep := make([]byte, N)
for i := 0; i < N; i += 2 {
rep[i] = 'Y'
rep[i+1] = 'V'
}
return rep
}
if Y < V+1 {
return nil
}
Y -= V + 1
ll := make([]byte, V*2+1)
ll[0] = 'Y'
for i := 1; i < len(ll); i += 2 {
ll[i] = 'V'
}
for i := 2; i < len(ll); i += 2 {
ll[i] = 'Y'
}
V = 0
preList = append(preList, ll)
nY = Y + 1
}
assert(len(preList) <= 3)
preListMap := make(map[byte][]byte)
for _, ll := range preList {
preListMap[ll[0]] = ll
}
debug(fmt.Sprintf("%v", preListMap))
baseList := sortOutSimpleCase(nR, nY, nB)
if baseList == nil {
return nil
} else {
newList := make([]byte, 0, N)
for _, baseLet := range baseList {
if pl, exist := preListMap[baseLet]; exist {
for _, letter := range pl {
newList = append(newList, letter)
}
delete(preListMap, baseLet)
} else {
newList = append(newList, baseLet)
}
}
return newList
}
}
type LetterAndNumber struct {
letter byte
number int
}
func sortOutSimpleCase(R, Y, B int) []byte {
colors := make([]LetterAndNumber, 3)
colors[0] = LetterAndNumber{'R', R}
colors[1] = LetterAndNumber{'Y', Y}
colors[2] = LetterAndNumber{'B', B}
sort.Slice(colors, func(i, j int) bool {
return colors[i].number > colors[j].number
})
dbgStr := make([]string, 0)
for _, c := range colors {
dbgStr = append(dbgStr, fmt.Sprintf("%v %v", string(c.letter), c.number))
}
debug(strings.Join(dbgStr, ", "))
if colors[0].number == 0 {
return make([]byte, 0)
}
if colors[1].number == 0 {
return nil
}
list := make([]byte, R+Y+B)
for a := 0; a < len(list); a++ {
list[a] = '_'
}
var i int
for i = 0; i < len(list)-1; i += 2 {
list[i] = colors[0].letter
colors[0].number--
if colors[0].number == 0 {
break
}
}
if colors[0].number > 0 {
return nil
}
i += 2
if i >= len(list) {
i = 1
} else {
for ; i < len(list); i += 2 {
if colors[1].number == 0 {
panic("!")
}
list[i] = colors[1].letter
colors[1].number--
}
}
i = 1
for ; i < len(list); i += 2 {
if colors[1].number > 0 {
list[i] = colors[1].letter
colors[1].number--
} else {
assert(colors[2].number > 0)
list[i] = colors[2].letter
colors[2].number--
}
}
for _, l := range list {
assert(l != '_')
}
return list
}
Wrong solution
func start() {
}
func test() {
var N, R, O, Y, G, B, V int
mustReadLineOfInts(&N, &R, &O, &Y, &G, &B, &V)
circle := make([]byte, 0, N)
debug(string(circle))
flag := false
for {
madeChanges := false
if R > 0 {
if len(circle) == 0 {
circle = append(circle, 'R')
R--
madeChanges = true
} else {
for i := 0; i < len(circle); i++ {
l := circle[i]
r := circle[(i+1)%len(circle)]
if l != 'R' && l != 'O' && l != 'V' && r != 'R' && r != 'O' && r != 'V' {
if i == len(circle)-1 {
circle = append(circle, 'R')
} else {
circle = append(circle, '_')
copy(circle[i+2:], circle[i+1:len(circle)-1])
circle[i+1] = 'R'
}
R--
madeChanges = true
break
}
}
}
}
if O > 0 {
if len(circle) == 0 {
circle = append(circle, 'O')
O--
madeChanges = true
}
}
if Y > 0 {
if len(circle) == 0 {
circle = append(circle, 'Y')
Y--
madeChanges = true
} else {
for i := 0; i < len(circle); i++ {
l := circle[i]
r := circle[(i+1)%len(circle)]
if l != 'Y' && l != 'O' && l != 'G' && r != 'Y' && r != 'O' && r != 'G' {
if i == len(circle)-1 {
circle = append(circle, 'Y')
} else {
circle = append(circle, '_')
copy(circle[i+2:], circle[i+1:len(circle)-1])
circle[i+1] = 'Y'
}
Y--
madeChanges = true
break
}
}
}
}
if G > 0 {
if len(circle) == 0 {
circle = append(circle, 'G')
G--
madeChanges = true
}
}
if B > 0 {
if len(circle) == 0 {
circle = append(circle, 'B')
B--
madeChanges = true
} else {
for i := 0; i < len(circle); i++ {
l := circle[i]
r := circle[(i+1)%len(circle)]
if l != 'B' && l != 'G' && l != 'V' && r != 'B' && r != 'G' && r != 'V' {
if i == len(circle)-1 {
circle = append(circle, 'B')
} else {
circle = append(circle, '_')
copy(circle[i+2:], circle[i+1:len(circle)-1])
circle[i+1] = 'B'
}
B--
madeChanges = true
break
}
}
}
}
if V > 0 {
if len(circle) == 0 {
circle = append(circle, 'V')
V--
madeChanges = true
}
}
if !madeChanges {
if flag {
break
} else {
flag = true
}
} else {
flag = false
}
debug(string(circle))
}
if len(circle) == N {
stdout.WriteString(string(circle))
stdout.WriteByte('\n')
} else {
stdout.WriteString("IMPOSSIBLE\n")
}
}
1
4 2 0 2 0 0 0
Sample test cases given in question
4
6 2 0 2 0 2 0
3 1 0 2 0 0 0
6 2 0 1 1 2 0
4 0 0 2 0 0 2
Other files
Case #1: RYRY