Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Google Code Jam
- * 2016 Qualification Round
- * Problem A. Counting Sheep
- * AQ <aq@okaq.com>
- */
- package main
- import (
- "bufio"
- "fmt"
- "os"
- "strconv"
- "strings"
- "sync"
- "time"
- )
- const (
- IN = "A-large-practice.in"
- OUT = "A-large-practice.out"
- )
- var (
- I *os.File
- O *os.File
- S *bufio.Scanner
- W *bufio.Writer
- T int
- WG sync.WaitGroup
- Sh []*Sheep
- )
- type Sheep struct {
- Id int // case number
- N int // starting number
- C int // current count
- M []string // accumulator
- S int // solution
- }
- func NewSheep() *Sheep {
- // return &Sheep{}
- // create new
- s := &Sheep{}
- s.C = 1
- s.M = make([]string, 10)
- copy(s.M, strings.Split("0123456789", ""))
- return s
- }
- func (s *Sheep) Solve() {
- // count
- if s.N == 0 {
- s.S = 0
- WG.Done()
- return
- }
- for {
- n0 := s.N * s.C
- // convert n to string
- n1 := strconv.Itoa(n0)
- n2 := strings.Split(n1, "")
- for i := 0; i < len(n2); i++ {
- b0, a0 := Remove(n2[i], s.M)
- // copy(s.M, a0)
- s.M = a0
- if b0 == true {
- // fmt.Println(s.Id, s.M, a0, b0)
- if len(s.M) == 0 {
- // done
- s.S = n0
- WG.Done()
- return
- }
- }
- }
- // remove from accumulator
- // check size
- s.C = s.C + 1
- }
- // s.S = 0
- // s.S = S.C * s.N
- // WG.Done()
- }
- func Remove(s string, a []string) (bool, []string) {
- // check if s in a
- // if so remove and return new and true
- // else return original and false
- for i := 0; i < len(a); i++ {
- if s == a[i] {
- b1 := true
- a1 := append(a[:i], a[i+1:]...)
- return b1, a1
- }
- }
- return false, a
- }
- func Load() {
- var err error
- I, err = os.Open(IN)
- if err != nil {
- fmt.Println(err)
- }
- S = bufio.NewScanner(I)
- O, err = os.Create(OUT)
- if err != nil {
- fmt.Println(err)
- }
- W = bufio.NewWriter(O)
- }
- func Cases() {
- var err error
- S.Scan()
- T, err = strconv.Atoi(S.Text())
- if err != nil {
- fmt.Println(err)
- }
- fmt.Printf("%d test cases. \n", T)
- }
- func Split() {
- var err error
- Sh = make([]*Sheep, T)
- for i := 0; i < T; i++ {
- s := NewSheep()
- S.Scan()
- s.N, err = strconv.Atoi(S.Text())
- if err != nil {
- fmt.Println(err)
- }
- s.Id = i + 1
- // fmt.Println(s)
- Sh[i] = s
- WG.Add(1)
- go Sh[i].Solve()
- }
- }
- func Finish() {
- defer I.Close()
- defer O.Close()
- for i := 0; i < T; i++ {
- s0 := ""
- if Sh[i].S == 0 {
- s0 = fmt.Sprintf("Case #%d: INSOMNIA\n", Sh[i].Id)
- } else {
- s0 = fmt.Sprintf("Case #%d: %d\n", Sh[i].Id, Sh[i].S)
- }
- W.WriteString(s0)
- }
- W.Flush()
- }
- func main() {
- begin := time.Now()
- Load()
- Cases()
- Split()
- WG.Wait()
- Finish()
- end := time.Now()
- fmt.Printf("total run time: %v.\n", end.Sub(begin))
- }
- // naive simulation with string arrays
- // total run time large data set: 2ms
- // watch out for slice copy repeating values
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement