結果

問題 No.3 ビットすごろく
ユーザー kuromook
提出日時 2016-06-06 22:49:19
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
MLE  
実行時間 -
コード長 1,435 bytes
コンパイル時間 553 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 525,864 KB
最終ジャッジ日時 2024-10-08 16:47:25
合計ジャッジ時間 7,236 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def go(n):
    ary = list(format(n,'b'))
    g = sum([int(a) for a in ary])
    return g


def sugoroku_map(val,debug=False):
    dic = {a:[a+go(a), a-go(a)] for a in range(1,val)}
    if debug:
        print(dic)
    return dic

def update_tree(val,dic, ary=[[1]]):
    reary = []
    flag = False
    for a in ary:
        b =list(a) 
        last = a[-1]
        if last in dic:
            el = dic[last]
            if val in el:
                flag = True
            if last == val:
                reary.append(a)
            else:
                # foward
                if (el[0] <= val) and (el[0] > 1) and (el[0] not in a):
                    a.append(el[0])
                    reary.append(a)
                # back
                if (el[1] <= val) and (el[1] > 1) and (el[1] not in b):
                    b.append(el[1])
                    reary.append(b)
        else:
            reary.append(a)
    return flag, reary


def main(debug=False):
    val = input()
    val = int(val)
    # make tree
    tree = [[1]]
    sugo_map=sugoroku_map(val, debug)
    for i in range(1,val):
        flag, tree = update_tree(val,sugo_map,tree)
        if debug:
            print(tree)
        if flag:
            print(len(tree[0]))
            return
    # tree length 
    length = [len(el) for el in tree if el[-1] == val]
    if len(length) > 0:
        print(min(length))
    else:
        print(-1)

main(debug=False)
0