[GO] ABC182

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.

Reference URL

I referred to here for standard input, and here for full bit search. Thank you very much.