結果
問題 | No.3 ビットすごろく |
ユーザー | kjnho |
提出日時 | 2017-02-19 13:48:23 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 322 ms / 5,000 ms |
コード長 | 991 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 10,964 KB |
実行使用メモリ | 58,636 KB |
最終ジャッジ日時 | 2023-09-14 00:20:18 |
合計ジャッジ時間 | 15,889 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 308 ms
58,332 KB |
testcase_01 | AC | 306 ms
58,096 KB |
testcase_02 | AC | 303 ms
58,320 KB |
testcase_03 | AC | 316 ms
58,160 KB |
testcase_04 | AC | 302 ms
58,180 KB |
testcase_05 | AC | 306 ms
58,348 KB |
testcase_06 | AC | 303 ms
58,044 KB |
testcase_07 | AC | 305 ms
58,028 KB |
testcase_08 | AC | 312 ms
58,160 KB |
testcase_09 | AC | 309 ms
58,416 KB |
testcase_10 | AC | 322 ms
58,348 KB |
testcase_11 | AC | 313 ms
58,296 KB |
testcase_12 | AC | 318 ms
58,244 KB |
testcase_13 | AC | 309 ms
57,968 KB |
testcase_14 | AC | 314 ms
58,248 KB |
testcase_15 | AC | 319 ms
58,160 KB |
testcase_16 | AC | 319 ms
58,116 KB |
testcase_17 | AC | 313 ms
58,400 KB |
testcase_18 | AC | 299 ms
58,208 KB |
testcase_19 | AC | 316 ms
58,264 KB |
testcase_20 | AC | 321 ms
58,136 KB |
testcase_21 | AC | 304 ms
58,080 KB |
testcase_22 | AC | 318 ms
58,384 KB |
testcase_23 | AC | 319 ms
58,408 KB |
testcase_24 | AC | 315 ms
58,348 KB |
testcase_25 | AC | 313 ms
58,336 KB |
testcase_26 | AC | 293 ms
57,932 KB |
testcase_27 | AC | 298 ms
58,144 KB |
testcase_28 | AC | 311 ms
58,252 KB |
testcase_29 | AC | 300 ms
58,636 KB |
testcase_30 | AC | 295 ms
58,092 KB |
testcase_31 | AC | 295 ms
58,060 KB |
testcase_32 | AC | 311 ms
58,308 KB |
ソースコード
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)