#![allow(unused_imports, unused_variables, dead_code, non_snake_case, unused_macros)] use std::io::{stdin, Read, StdinLock}; use std::str::FromStr; use std::fmt::*; use std::str::*; use std::cmp::*; use std::collections::*; fn getline() -> String{ let mut res = String::new(); std::io::stdin().read_line(&mut res).ok(); res } macro_rules! readl { ($t: ty) => { { let s = getline(); s.trim().parse::<$t>().unwrap() } }; ($( $t: ty),+ ) => { { let s = getline(); let mut iter = s.trim().split(' '); ($(iter.next().unwrap().parse::<$t>().unwrap(),)*) } }; } macro_rules! readlvec { ($t: ty) => { { let s = getline(); let iter = s.trim().split(' '); iter.map(|x| x.parse().unwrap()).collect::>() } } } macro_rules! mvec { ($v: expr, $s: expr) => { vec![$v; $s] }; ($v: expr, $s: expr, $($t: expr),*) => { vec![mvec!($v, $($t),*); $s] }; } macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } } fn printiter<'a, T>(v: &'a T) where &'a T: std::iter::IntoIterator, <&'a T as std::iter::IntoIterator>::Item: std::fmt::Display { for (i,e) in v.into_iter().enumerate() { if i != 0 { print!(" "); } print!("{}", e); } println!(""); } struct ContestPrinter { s: String, } impl ContestPrinter { fn new() -> ContestPrinter { ContestPrinter { s: String::new(), } } fn print(&mut self, x: T) where T: std::fmt::Display { self.s.push_str(format!("{}", x).as_str()); } fn println(&mut self, x: T) where T: std::fmt::Display { self.s.push_str(format!("{}\n", x).as_str()); } } impl std::ops::Drop for ContestPrinter { fn drop(&mut self) { print!("{}", self.s); } } fn is_max_i64(num: i64) -> bool { if num == i64::max_value() { true } else { false } } // fn knapsack_equal(ws: &Vec, sum: usize, possible_sum: usize) -> bool { let possible_sum = 100 * 100 + 1; let N1 = ws.len() + 1; let mut dp = vec![vec![false; possible_sum]; N1]; dp[0][0] = true; for i in 1..N1 { let w = ws[i-1]; for j in 0..possible_sum { if j >= w { dp[i][j] = dp[i - 1][j] | dp[i - 1][j - w]; } else { dp[i][j] = dp[i - 1][j]; } } } dp[N1-1][sum] } fn main() { let mut pr = ContestPrinter::new(); let N = readl!(usize); let ws = readlvec!(usize); let sum = ws.iter().fold(0, |sum, x| sum + x); if (sum % 2) != 0 { pr.println("impossible"); return; } let possible_sum = 100 * 100 + 1; pr.println( if knapsack_equal(&ws, sum / 2, possible_sum) { "possible" } else { "impossible" } ); }