結果

問題 No.3 ビットすごろく
ユーザー TakashinaInHubTakashinaInHub
提出日時 2016-01-30 18:21:01
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,189 bytes
コンパイル時間 406 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 20,128 KB
最終ジャッジ日時 2024-09-21 19:26:40
合計ジャッジ時間 7,091 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 86 ms
12,288 KB
testcase_01 AC 91 ms
12,288 KB
testcase_02 AC 87 ms
12,160 KB
testcase_03 AC 93 ms
12,032 KB
testcase_04 TLE -
testcase_05 -- -
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 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def steps(n)
    i = 0
    while n > 0
        i += 1 if n%2 == 1
        n >>=  1
    end
    i
end

def mapping(n, p)
    dis = steps(p)
    fowdis = p + dis
    backdis = p - dis
    map = Array.new(2, -1)
    map[0] = fowdis if fowdis <= n
    map[1] = backdis if 1 <= backdis
    map
end

def bitsize(n)
    i = 0
    while n > 0 do i += 1; n >>= 1 end
    i
end

def scanrange(n)
    bsize = bitsize(n)+1

    sn, en = n-bsize, n+bsize
    sn = 1 if sn < 1
    sn..en
end

def scanroot(map_list, n, x=0)
    return n if n == 1
    return -1 if x > map_list.length
    
    #このマスに到達可能なマスのリストアップ
    rlist = Array.new
    scanrange(n).each { |i|
        break if i > map_list.length
        2.times { |p| rlist << i if map_list[i-1][p] == n }
    }
    
    return -1 if rlist.length == 0
    
    #リストのリンク先を再スキャン
    min = map_list.length
    rlist.each { |i|
        c = scanroot(map_list, i, x+1)
        min = c if 0 < c and c < min
    }
    
    return -1 if min == map_list.length

    min + 1
end

n = gets.to_i
map_list = Array.new(n)
n.times { |i|
  map_list[i] = mapping(n, i+1)
}

puts scanroot(map_list, n)
0