# -*- coding: utf-8 -*- # !/usr/bin/env python # vim: set fileencoding=utf-8 : """ # # Author: Noname # URL: https://github.com/pettan0818 # License: MIT License # Created: 金 9/28 23:04:27 2018 # Usage # """ from collections import deque def get(): """ """ return int(input()) def get_each_cell_num(length): """ >>> get_each_cell_num(5) [1, 1, 2, 1, 2] """ def maker(num): return sum([int(i) for i in list(bin(num)[2:])]) return [maker(i) for i in range(1, length+1)] def bfs(res, goal, route): QUE = deque([]) goal = goal - 1 # 配列と問題文のIndexは1差がある。 res[0] = 0 counter = 1 QUE.append(0) while QUE: # Listが空だとFalse # print(res) counter += 1 pos = QUE.popleft() # print(pos) if pos == goal: # ゴールに着いたら探索不要 return res for i in [route[pos], -route[pos]]: next_pos = pos + i if next_pos >= len(res): continue if res[next_pos] != -1: continue if next_pos >= 0: QUE.append(next_pos) print("next_pos: ", next_pos) print("res: ", res) print("QUE: ", QUE) res[next_pos] = counter return res def solve(length): """ >>> solve(5) """ res = [-1] * length route = get_each_cell_num(length) a = bfs(res,length, route) print(a[-1]) if __name__ == '__main__': solve(get())