結果

問題 No.3 ビットすごろく
コンテスト
ユーザー TakashinaInHub
提出日時 2016-01-30 18:27:03
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,361 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 14,016 KB
最終ジャッジ日時 2024-09-21 19:27:10
合計ジャッジ時間 7,298 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
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
		#"puts "#{n} : bitsize->#{bsize}" if false

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

def scanroot(map_list, n, x=0, min=map_list.length)
    return n if n == 1
    return -1 if x > min
    
    #このマスに到達可能なマスのリストアップ
    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 }
    }
    
    #if false then  rlist.each { |i| puts "#{i} : #{map_list[i-1]}" }; end
    return -1 if rlist.length == 0
    
    #リストのリンク先を再スキャン
    min = map_list.length
    rlist.each { |i|
        #puts "Start #{i}" if false
        c = scanroot(map_list, i, x+1, min)
        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