結果

問題 No.3 ビットすごろく
ユーザー seiichiseiichi
提出日時 2021-01-14 14:46:32
言語 Go
(1.22.1)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 1 ms
5,376 KB
testcase_22 AC 3 ms
5,376 KB
testcase_23 AC 4 ms
5,376 KB
testcase_24 AC 4 ms
5,376 KB
testcase_25 AC 4 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 4 ms
5,376 KB
testcase_29 AC 3 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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)
}
0