結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2021-01-03 16:33:34 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,688 bytes |
コンパイル時間 | 13,286 ms |
コンパイル使用メモリ | 220,292 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 10:01:49 |
合計ジャッジ時間 | 14,362 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
package mainimport ("fmt""strconv")func scan() (N int) {fmt.Scan(&N)return}func countBit(i int) (count int) {s := strconv.FormatInt(int64(i), 2)for _, c := range s {if c == '1' {count++}}return count}func getCount(i int, passed []bool, N int, count int) int {if i == N {return count}if i < 1 || i > N || passed[i] == true {return -1}count++passed[i] = truestep := countBit(i)fowardStep := i + stepbackwardStep := i - stepfowardCount := getCount(fowardStep, passed, N, count)backwardCount := getCount(backwardStep, passed, N, count)if fowardCount < 0 || backwardCount < 0 {if fowardCount > backwardCount {return fowardCount} else {return backwardCount}} else {if fowardCount < backwardCount {return fowardCount} else {return backwardCount}}}type Info struct {count intposition int}func main() {var N intN = scan()// N = 11passed := make([]bool, N)var queue []Infoa := Info{count: 1, position: 1}queue = append(queue, a)result := Info{count: -1}for len(queue) > 0 {info := queue[0]queue = queue[1:]if info.position == N {result = infobreak}if info.position < 1 || info.position > N || passed[info.position] == true {continue}count := info.count + 1passed[info.position] = truestep := countBit(info.position)fowardStep := info.position + stepfowardInfo := Info{count: count, position: fowardStep}queue = append(queue, fowardInfo)backwardStep := info.position - stepbackwardInfo := Info{count: count, position: backwardStep}queue = append(queue, backwardInfo)}fmt.Print(result.count)}