AtCoder Beginner Contest 182 C - To 3 https://atcoder.jp/contests/abc182/tasks/abc182_c
package main
import(
"fmt"
"bufio"
"os"
"strconv"
"strings"
)
var rdr=bufio.NewReaderSize(os.Stdin,1024*1024)
func readLine() string {
buf := []byte{}
for {
l, p, e := rdr.ReadLine()
if e != nil {
panic(e)
}
buf = append(buf, l...)
if !p {
break
}
}
return string(buf)
}
func readInts()[]int{
s:=strings.Split(readLine()," ")
res:=[]int{}
for _,v:=range s{
i,_:=strconv.Atoi(v)
res=append(res,i)
}
return res
}
func main(){
s:=strings.Split(readLine(),"")
//Since there are a maximum of 18 digits that are not used, 18+1=19
minK:=19
n:=len(s)
for bits:=0;bits<(1<<uint64(n));bits++{
var cp=make([]string,n)
//The original will change, so copy it one by one
copy(cp,s)
k:=0
sums:=0
for i:=0;i<n;i++{
if (bits>>uint64(i))&1==1{
k++
}else{
j,_:=strconv.Atoi(s[i])
sums+=j
}
}
if sums%3==0 && minK>k{
minK=k
}
}
if minK==n{
fmt.Println(-1)
}else{
fmt.Println(minK)
}
}
・ If the sum of each digit is divisible by 3, it must be a multiple of 3. ・ If you want to search all the digits that you do not want to use, use bit full search. Considering the above, I solved it when I did a full bit search.
I referred to here for standard input, and here for full bit search. Thank you very much.
Recommended Posts