#!/usr/bin/rubyrequire 'rubygems'require 'multiset' # run "gem install multiset" firstdef check l, h, freqs lb, ub = nil, Multiset.new freqs.each do |x| # factor comes with GNU coreutils; any GNU setup should have it. factors = Multiset.new %x(factor #{x}).sub(/.*:/, '').split.map(&:to_i) if x >= l lb = lb ? lb & factors : factors else ub |= factors end end lbn = lb && lb.reduce(:*) ubn = ub.reduce(1, :*) if lb && lb.empty? # no suitable lower bound return l == 1 ? 1 : nil end return nil if lbn && lbn < l # no suitable lower bound return nil if lb && (ub & lb) != ub # upper and lower bounds incompatible sl, sh = (l + ubn - 1) / ubn, h / ubn return nil if sh < sl # range is too narrow to fit upper bound return sl * ubn unless lb && lb != ub # happy case # Here, we get the factors that sit between ub and lb and try to # find a combination that's between l and h. bt = lb - ub btn = bt.reduce(1, :*) return nil if btn < sl bta = bt.to_a.sort result = [] (1 << bta.size).times do |n| prod = bta.select do |*| res = n & 1 n >>= 1 res != 0 end.reduce(1, :*) if prod >= sl && prod <= sh result << prod * ubn end end result.minendT = gets.to_iT.times do |c| n, l, h = gets.split.map &:to_i freqs = gets.split.map &:to_i result = check l, h, freqs if result puts "Case ##{c + 1}: #{result}" else puts "Case ##{c + 1}: NO" endend