$n = gets.to_i $w = gets.split.map(&:to_i) $nerai = $w.inject(:+)/2.0 $dp = Array.new($n){Array.new(100*100+1, nil)} def dfs(depth, total) if depth >= $n - 1 return 1 if total + $w[depth] == $nerai return 1 if total == $nerai return -1 end $dp[depth+1][total+$w[depth]] ||= dfs(depth+1, total+$w[depth]) $dp[depth+1][total] ||= dfs(depth+1, total) return $dp[depth+1][total+$w[depth]] if $dp[depth+1][total+$w[depth]] return $dp[depth+1][total] if $dp[depth+1][total] return -1 end puts dfs(-1, 0) > 0 ? "possible" : "impossible"