結果
| 問題 | No.3 ビットすごろく |
| ユーザー |
 kjnho
|
| 提出日時 | 2017-02-19 13:16:05 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,082 bytes |
| コンパイル時間 | 148 ms |
| コンパイル使用メモリ | 12,800 KB |
| 実行使用メモリ | 18,592 KB |
| 最終ジャッジ日時 | 2024-06-09 14:19:00 |
| 合計ジャッジ時間 | 9,801 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 33 ms
11,008 KB |
| testcase_01 | AC | 35 ms
10,880 KB |
| testcase_02 | AC | 34 ms
10,880 KB |
| testcase_03 | AC | 2,737 ms
11,392 KB |
| testcase_04 | AC | 275 ms
11,008 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 | -- | - |
ソースコード
from heapq import heappop, heappush, heapify
from copy import deepcopy as dcopy
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)