MAX_N = 100 MAX_W = 100 def main n = gets.to_i w_list = gets.split.map(&:to_i) w_sum = w_list.inject(:+) return "impossible" if w_sum % 2 == 1 dp = [false] * (MAX_N * MAX_W + 1) dp[0] = true w_list.each do |w| (MAX_N * MAX_W - w).downto(0) do |i| dp[i+w] = true if dp[i] end end if dp[w_sum/2] return "possible" else return "impossible" end end puts main()