hitori-game .devquiz2011

hitori-game.rb

=begin
入力形式
T             ケースの数(1<=T<=100)
N             ケース1の数の個数(1<=N<=10)
a1 a2 ... aN  与えられる数(0<=an<=1,000,000)
M             ケース2の数の個数
b1 b2 ... bM  与えられる数
...           ...
=end


#coding: utf-8

INF = 30

#question == [[a1,a2,...,aN],[b1,b2,...,bM],...]
master_text_array = Array.new
File.open(ARGV[0]) do |io|
   while text = io.gets
      master_text_array.push(text)
   end
end
question = Array.new((master_text_array.length - 1) / 2)
question.each_index do |x|
   question[x] = Array.new
   question[x] = master_text_array[2*x+2].split.map! { |ch| ch.to_i } 
end 

#BFS
#既出の状態になるときと、5の倍数を消しても状態が変わらないときだけ切る
def conclusion (start)
   que = Array.new
   m = Hash.new(INF)
   que.push(start)
   m[start] = 0

   while que.length
      state  = que.shift
      if (state.length == 0)
         break
      end
   
      temp1 = state.map { |item| item / 2 }
      temp2 = state.reject { |item| item % 5 == 0 }
      if (m[temp1] == INF)
        que.push(temp1)
        m[temp1] = m[state] + 1
      end
      if (m[temp2] == INF && state.length != temp2.length)
         que.push(temp2)
         m[temp2] = m[state] + 1
      end
   end
   return m[[]] 
end

File.open("ARGV[1]", "w") do |text|
  question.each do |item|
     text.puts(conclusion(item))
  end  
end