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.

Recommended Posts

ABC168
ABC164
ABC174
ABC175
ABC170
ABC182
ABC153
ABC146 Impressions
ABC167 WriteUp
AtCoder ABC177
Beginner ABC154 (Python)
Beginner ABC156 (Python)
abc154 participation report
abc155 participation report
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
Beginner ABC155 (Python)
Beginner ABC157 (Python)
AtCoder ABC 175 Python
Looking back on ABC155
Atcoder ABC115 Past Exercises
Solve ABC169 in Python
ABC147 C --HonestOrUnkind2 [Python]