# coding: utf-8 # おもりのリストのクラス class Omoris # 初期化時にソートする。 def initialize(list) @list = list.sort # その前での合計リスト @sum_list = @list.inject([]) do |m, i| m << m.last.to_i + i end # 結果のキャッシュ @cache = {} end # おもりの合計を返す。 def sum(index = -1) @sum_list[index] end # end番目以前の組み合わせで合計がtargetになるか? def check(target, last) if @cache.has_key?([target, last]) return @cache[[target, last]] end # 0なら合致しているのでOK return true if target == 0 # 最後の前まで調べる。 (0..last).to_a.reverse.each do |i| if target > @sum_list[i] # 全部足しても届かない @cache[[target, last]] = false return false elsif target == @sum_list[i] # 全部足すと一致 @cache[[target, last]] = true return true elsif i < last && @list[i + 1] == @list[i] # 2回目以降で前と一緒なら調べる必要なし。 next elsif target < @list[i] # 越えちゃったので次を調べる。 next else # 少ないときはtargetから今の分を減らして、さらにcheckする。 if check(target - @list[i], i - 1) # 合致したのでOK。 @cache[[target, last]] = true return true else # あわなくても次を調べる。 next end end end # 一致なし @cache[[target, last]] = false return false end # 重りのインデックス def [](index) @list[index] end # 重りの数 def size @list.size end end # 1行目はRubyでは不要。 gets # 数字のリストを取得。 omoris = Omoris.new(gets.split.map(&:to_i)) sum = omoris.sum # 合計が偶数で無いと組み合わせは無い。 # 2個以上重りが無いと組み合わせは無い。 # 一番大きい重りが半分以下で無いと組み合わせは無い。 # 合計の半分の組み合わせをチェックする。 if sum.even? && omoris.size > 1 && omoris[-1] <= sum / 2 && omoris.check((sum / 2 - omoris[-1]), omoris.size - 2) puts "possible" else puts "impossible" end