# coding: utf-8 # おもりのリストのクラス class Omoris # 初期化時にソートする。 def initialize(list) @list = list.sort end # おもりの合計を返す。 def sum @list.inject {|sum, i| sum + i} end # end番目以前の組み合わせで合計がtargetになるか? def check(target, last) # 0なら合致しているのでOK return true if target == 0 # 最後の前まで調べる。 (1..last).to_a.reverse.each do |i| if 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。 return true else # あわなくても次を調べる。 next end end end # 1番最初の時を調べる。 if target == @list[0] return true else return false end 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