結果
問題 | No.3 ビットすごろく |
ユーザー | kjnho |
提出日時 | 2017-02-19 13:51:27 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 317 ms / 5,000 ms |
コード長 | 991 bytes |
コンパイル時間 | 81 ms |
コンパイル使用メモリ | 10,908 KB |
実行使用メモリ | 58,528 KB |
最終ジャッジ日時 | 2023-09-14 00:20:51 |
合計ジャッジ時間 | 11,675 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 294 ms
58,004 KB |
testcase_01 | AC | 302 ms
57,984 KB |
testcase_02 | AC | 298 ms
58,064 KB |
testcase_03 | AC | 301 ms
57,992 KB |
testcase_04 | AC | 298 ms
58,288 KB |
testcase_05 | AC | 298 ms
58,264 KB |
testcase_06 | AC | 293 ms
58,384 KB |
testcase_07 | AC | 289 ms
57,932 KB |
testcase_08 | AC | 298 ms
58,176 KB |
testcase_09 | AC | 299 ms
58,312 KB |
testcase_10 | AC | 299 ms
58,492 KB |
testcase_11 | AC | 304 ms
58,272 KB |
testcase_12 | AC | 304 ms
58,124 KB |
testcase_13 | AC | 307 ms
57,936 KB |
testcase_14 | AC | 317 ms
57,996 KB |
testcase_15 | AC | 316 ms
58,332 KB |
testcase_16 | AC | 317 ms
58,368 KB |
testcase_17 | AC | 313 ms
58,364 KB |
testcase_18 | AC | 300 ms
57,896 KB |
testcase_19 | AC | 312 ms
58,528 KB |
testcase_20 | AC | 294 ms
58,276 KB |
testcase_21 | AC | 297 ms
57,944 KB |
testcase_22 | AC | 309 ms
58,312 KB |
testcase_23 | AC | 314 ms
58,384 KB |
testcase_24 | AC | 309 ms
58,388 KB |
testcase_25 | AC | 311 ms
58,160 KB |
testcase_26 | AC | 296 ms
57,952 KB |
testcase_27 | AC | 301 ms
57,960 KB |
testcase_28 | AC | 305 ms
58,340 KB |
testcase_29 | AC | 305 ms
58,240 KB |
testcase_30 | AC | 298 ms
58,144 KB |
testcase_31 | AC | 298 ms
58,208 KB |
testcase_32 | AC | 310 ms
58,308 KB |
ソースコード
import re from scipy import integrate from operator import itemgetter from collections import defaultdict as dd from collections import Counter import numpy as np import fractions import itertools import math import heapq from collections import deque 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)