結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2017-02-19 13:48:23 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,541 ms / 5,000 ms |
コード長 | 991 bytes |
コンパイル時間 | 105 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 69,660 KB |
最終ジャッジ日時 | 2024-07-01 08:18:20 |
合計ジャッジ時間 | 56,534 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
外部呼び出し有り |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import re from scipy import integrate from operator import itemgetter from collections import defaultdict as dd from collections import Counter from collections import deque import numpy as np import fractions import itertools import math import heapq from heapq import heappop, heappush, heapify from copy import deepcopy as dcopy N = int(input()) # N = 5000 stack = deque() stack.append((1, 0)) # count, position, arrived, root D = [1] + [float("inf")]*(N-1) # saitankyorimap flag = False while len(stack) != 0: count, position = stack.popleft() number = position + 1 if number == N: print(count) flag = True break move_size = bin(number).count("1") for move in (move_size, - move_size): new_position = position + move new_count = count + 1 if (0 <= new_position <= N-1) and D[new_position] > count: D[new_position] = count stack.append((new_count, new_position)) if not flag: print(-1)