プログラミングコンテストチャレンジブック演習「くじ引き」

今回のお題はこちら

$kuji = [1, 2, 3, 4, 10, 30, 2]
N = $kuji.length - 1
m = 100

def GetAllKcKdConbination()
  kujiSubset = Array.new
  for i in 0..N
    for j in i..N
      kujiSubset.push($kuji[i] + $kuji[j])
    end
  end
  return kujiSubset.sort
end

def binarySearch(target, array)
  low = 0
  high = array.length - 1
  while(high - low >= 1)
    pos = ((low + high) / 2).truncate
    if array[pos] == target
      return true
    elsif array[pos] < target
      low = pos + 1
    else
      high = pos - 1
    end
  end
  return false
end

allKcKd = GetAllKcKdConbination()

for i in 0..N
  for j in 0..N
    if binarySearch(m - $kuji[i] - $kuji[j], allKcKd)
      puts "YES"
      exit(0)
    end
  end
end

puts "NO"