結果
問題 | No.3 ビットすごろく |
ユーザー | kjnho |
提出日時 | 2017-02-19 13:14:18 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,335 bytes |
コンパイル時間 | 133 ms |
コンパイル使用メモリ | 10,980 KB |
実行使用メモリ | 63,088 KB |
最終ジャッジ日時 | 2023-08-28 19:08:04 |
合計ジャッジ時間 | 11,601 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 286 ms
58,100 KB |
testcase_01 | AC | 284 ms
58,180 KB |
testcase_02 | AC | 286 ms
57,736 KB |
testcase_03 | AC | 2,852 ms
58,544 KB |
testcase_04 | AC | 522 ms
57,920 KB |
testcase_05 | TLE | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
ソースコード
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 from copy import deepcopy as dcopy import heapq from heapq import heappop, heappush, heapify N = int(input()) # N = 5 stack = [] heappush(stack, (1, 0, [True]+[False]*(N-1), "1")) # count, position, arrived, root D = [1] + [float("inf")]*(N-1) # saitankyorimap flag = False while len(stack) != 0: count, position, arrived, root = heappop(stack) 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 new_arrived = dcopy(arrived) new_root = root + str(new_position + 1) if not (0 <= new_position <= N-1): pass elif new_arrived[new_position]: pass elif D[new_position] <= count: pass else: new_arrived[new_position] = True D[new_position] = count # print(new_root) heappush(stack, (new_count, new_position, new_arrived, new_root)) if not flag: print(-1)