結果

問題 No.3 ビットすごろく
ユーザー seiichi
提出日時 2021-01-14 14:46:32
言語 Go
(1.23.4)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,150 bytes
コンパイル時間 11,751 ms
コンパイル使用メモリ 233,344 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 10:02:06
合計ジャッジ時間 13,010 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
"fmt"
"strconv"
)
func scan() (N int) {
fmt.Scan(&N)
return
}
func calcSteps(position int) (steps int) {
s := strconv.FormatInt(int64(position), 2)
for _, c := range s {
if c == '1' {
steps++
}
}
return
}
type Item struct {
currentPosition int
numOfSteps int
}
func main() {
N := scan()
// N := 4
result := -1
visited := map[int]bool{}
var queue []Item
queue = append(queue, Item{
currentPosition: 1,
numOfSteps: 1,
})
for len(queue) > 0 {
item := queue[0]
queue = queue[1:]
if item.currentPosition == N {
result = item.numOfSteps
break
} else if item.currentPosition < 1 || item.currentPosition > N {
continue
} else if visited[item.currentPosition] {
continue
}
visited[item.currentPosition] = true
steps := calcSteps(item.currentPosition)
// go foward
queue = append(queue, Item{
currentPosition: item.currentPosition + steps,
numOfSteps: item.numOfSteps + 1,
})
// go backward
queue = append(queue, Item{
currentPosition: item.currentPosition - steps,
numOfSteps: item.numOfSteps + 1,
})
}
fmt.Print(result)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0