Return to problem list2019-1C Problem A
Final solution
func start() {
}
func round(my, other byte) int8 {
switch my {
case 'R':
if other == 'P' {
return -1
} else if other == 'S' {
return 1
}
case 'P':
if other == 'S' {
return -1
} else if other == 'R' {
return 1
}
case 'S':
if other == 'R' {
return -1
} else if other == 'P' {
return 1
}
default:
panic("!")
}
return 0
}
func test() {
var A int
mustReadLineOfInts(&A)
otherPrograms := make([][]byte, A)
maxLen := A
for i := 0; i < A; i++ {
otherPrograms[i] = []byte(mustReadLine())
}
myProg := make([]byte, maxLen)
var next func(pos int, _defeatedOpponents []bool) bool
next = func(pos int, _defeatedOpponents []bool) bool {
opToTry := []byte{'R', 'P', 'S'}
opResult := make([]int8, 3)
opResult_defeatedComponent := make([][]bool, 3)
for i := 0; i < 3; i++ {
opResult_defeatedComponent[i] = make([]bool, len(_defeatedOpponents))
copy(opResult_defeatedComponent[i], _defeatedOpponents)
}
for i, myOp := range opToTry {
defeatedAll := true
lose := false
for opponentId, oppProgram := range otherPrograms {
if opResult_defeatedComponent[i][opponentId] {
continue
}
otherOp := oppProgram[pos%len(oppProgram)]
vsRes := round(myOp, otherOp)
if vsRes == 1 {
opResult_defeatedComponent[i][opponentId] = true
} else {
defeatedAll = false
}
if vsRes == -1 {
lose = true
break
}
}
if defeatedAll {
opResult[i] = 1
} else {
if lose {
opResult[i] = -1
} else {
opResult[i] = 0
}
}
}
for i, result := range opResult {
myProg[pos] = opToTry[i]
if result == 1 {
maxLen = pos + 1
return true
}
}
for i, result := range opResult {
myProg[pos] = opToTry[i]
if result == 0 {
if pos == maxLen-1 {
continue
}
if next(pos+1, opResult_defeatedComponent[i]) {
return true
}
}
}
return false
}
if next(0, make([]bool, A)) {
stdout.Write(myProg[:maxLen])
stdout.WriteByte('\n')
} else {
stdout.WriteString("IMPOSSIBLE\n")
}
}
Wrong solutions
wrong-1
func start() {
}
func test() {
var A int
mustReadLineOfInts(&A)
otherPrograms := make([][]byte, A)
maxLen := 0
for i := 0; i < A; i++ {
otherPrograms[i] = []byte(mustReadLine())
if len(otherPrograms[i]) > maxLen {
maxLen = len(otherPrograms[i])
}
}
myProg := make([]byte, maxLen)
defeated := make([]bool, A)
for i := 0; i < maxLen; i++ {
myActionCanBe := make(map[byte]bool)
myActionCanBe['R'] = true
myActionCanBe['P'] = true
myActionCanBe['S'] = true
for opponent, p := range otherPrograms {
if defeated[opponent] {
continue
}
if i < len(p) {
theirAction := p[i]
switch theirAction {
case 'R':
delete(myActionCanBe, 'S')
case 'P':
delete(myActionCanBe, 'R')
case 'S':
delete(myActionCanBe, 'P')
default:
panic(theirAction)
}
}
}
if len(myActionCanBe) == 0 {
stdout.WriteString("IMPOSSIBLE\n")
return
} else {
myAct := byte('_')
if len(myActionCanBe) == 1 {
for act, _ := range myActionCanBe {
myAct = act
break
}
myProg[i] = myAct
for opponent, theirProg := range otherPrograms {
if defeated[opponent] {
continue
}
if theirProg[i%len(theirProg)] != myAct {
defeated[opponent] = true
}
}
}
}
}
defeatedAll := true
for _, d := range defeated {
if !d {
defeatedAll = false
break
}
}
if !defeatedAll {
stdout.WriteString("IMPOSSIBLE\n")
} else {
stdout.Write(myProg)
stdout.WriteByte('\n')
}
}
wrong-2
func start() {
}
func test() {
var A int
mustReadLineOfInts(&A)
otherPrograms := make([][]byte, A)
maxLen := 0
for i := 0; i < A; i++ {
otherPrograms[i] = []byte(mustReadLine())
if len(otherPrograms[i]) > maxLen {
maxLen = len(otherPrograms[i])
}
}
myProg := make([]byte, maxLen)
check := func(upTo int) int8 {
defeated := make([]bool, A)
for ps := 0; ps <= upTo; ps++ {
allDefeated := true
for op := 0; op < A; op++ {
if defeated[op] {
continue
}
opProg := otherPrograms[op]
opAct := opProg[ps%len(opProg)]
myAct := myProg[ps]
switch myAct {
case 'R':
if opAct == 'P' {
return -1
} else if opAct == 'S' {
defeated[op] = true
}
case 'P':
if opAct == 'S' {
return -1
} else if opAct == 'R' {
defeated[op] = true
}
case 'S':
if opAct == 'R' {
return -1
} else if opAct == 'P' {
defeated[op] = true
}
}
if !defeated[op] {
allDefeated = false
}
}
if allDefeated {
return 1
}
}
return 0
}
var search func(currentUpTo int) bool
search = func(currentUpTo int) bool {
if currentUpTo == maxLen {
return false
}
toTry := []byte{'R', 'P', 'S'}
for _, try := range toTry {
myProg[currentUpTo] = try
ck := check(currentUpTo)
if ck == 1 {
maxLen = currentUpTo + 1
return true
} else if ck == -1 {
continue
} else {
if search(currentUpTo + 1) {
return true
}
}
}
return false
}
if search(0) {
stdout.Write(myProg[:maxLen])
stdout.WriteByte('\n')
} else {
stdout.WriteString("IMPOSSIBLE\n")
}
}
1
3
P
R
R
Solution that only works for the small input
func start() {
}
func test() {
var A int
mustReadLineOfInts(&A)
otherProgs := make([][]byte, A)
maxLen := A
for i := 0; i < A; i++ {
otherProgs[i] = []byte(mustReadLine())
}
myProg := make([]uint8, maxLen)
options := []byte{'R', 'S', 'P'}
for {
won := true
a:
for _, opponent := range otherProgs {
for i := 0; i < maxLen; i++ {
oppAction := opponent[i%len(opponent)]
myAction := options[myProg[i]]
res := round(myAction, oppAction)
if res == 1 {
break
}
if res == -1 {
won = false
break a
}
if res == 0 && i == maxLen-1 {
won = false
break a
}
}
}
if won {
for _, i := range myProg {
stdout.WriteByte(options[i])
}
stdout.WriteByte('\n')
return
} else {
ptr := maxLen - 1
for {
if myProg[ptr]+1 >= 3 {
myProg[ptr] = 0
ptr--
if ptr < 0 {
stdout.WriteString("IMPOSSIBLE\n")
return
}
} else {
myProg[ptr]++
break
}
}
}
}
}
func round(my, other byte) int8 {
switch my {
case 'R':
if other == 'P' {
return -1
} else if other == 'S' {
return 1
}
case 'P':
if other == 'S' {
return -1
} else if other == 'R' {
return 1
}
case 'S':
if other == 'R' {
return -1
} else if other == 'P' {
return 1
}
default:
panic("!")
}
return 0
}
Sample test cases given in question
3
1
RS
3
R
P
S
7
RS
RS
RS
RS
RS
RS
RS
Other files
Case #1: PS
2
2
RS
PRP
2
RP
PRP
Case #1: PP