#![allow(unused_imports)] use ac_library::{ModInt998244353 as mint, Segtree, dsu, modint}; use itertools::{Itertools, izip}; use my_library::*; use num::Float; // use omniswap::swap; // use permutohedron::LexicalPermutation; use proconio::{ fastout, input, marker::{Chars, Usize1}, }; use std::{ cmp::Reverse, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet}, }; // #[fastout] fn main() { input! { n : usize, w : [usize; n] } let sum = w.iter().sum::(); if sum % 2 == 1 { println!("impossible"); return; } let mut d = vec![false; sum / 2 + 1]; d[0] = true; for w in w { for i in (w..=sum / 2).rev() { d[i] |= d[i - w]; } } yes_no2(*d.last().unwrap(), "possible", "impossible"); } #[allow(dead_code)] mod my_library { use itertools::Itertools; use num::Bounded; // Utils pub fn yes_no(f: bool) { yes_no2(f, "Yes", "No"); } pub fn yes_no2(f: bool, yes: T, no: T) { println!("{}", if f { yes } else { no }); } pub fn print_vec(s: Vec, sep: &str) { println!("{}", s.iter().join(sep)); } pub trait ChangeMinMax { /// self より other が小さければ self を更新し、true を返す fn chmin(&mut self, other: Self) -> bool; /// self より other が大きければ self を更新し、true を返す fn chmax(&mut self, other: Self) -> bool; } // PartialOrd(順序比較可能)なすべての型に一括実装 impl ChangeMinMax for T { fn chmin(&mut self, other: Self) -> bool { if other < *self { *self = other; true } else { false } } fn chmax(&mut self, other: Self) -> bool { if other > *self { *self = other; true } else { false } } } pub fn print_vec_usize1(s: Vec, sep: &str) { let s = s.iter().map(|s| s + 1).collect_vec(); print_vec(s, sep); } pub fn tenti(matrix: &Vec>) -> Vec> { if matrix.is_empty() { return Vec::new(); } let h = matrix.len(); let w = matrix[0].len(); if w == 0 { return Vec::new(); } let mut res = vec![Vec::with_capacity(h); w]; for i in 0..h { for j in 0..w { res[j].push(matrix[i][j]); } } res } pub fn rotate_mat(matrix: &Vec>, dy: usize, dx: usize) -> Vec> { if matrix.is_empty() { return Vec::new(); } let h = matrix.len(); let w = matrix[0].len(); if w == 0 { return Vec::new(); } let mut res = matrix.clone(); res.rotate_left(dy); for i in 0..h { res[i].rotate_left(dx); } res } // Number Theory, Math pub fn gcd(a: u64, b: u64) -> u64 { if b == 0 { a } else { gcd(b, a % b) } } pub fn gcd_vec(v: &Vec) -> u64 { v.iter().fold(v[0], |f, x| gcd(*x, f)) } pub fn lcm(a: u64, b: u64) -> u64 { a / gcd(a, b) * b } pub fn lcm_vec(v: &Vec) -> u64 { v.iter().fold(v[0], |f, x| lcm(*x, f)) } pub fn prime_factors(mut n: u64) -> Vec<(u64, u32)> { let mut factors = Vec::new(); // 2 の素因数を処理 let count_2 = n.trailing_zeros(); if count_2 > 0 { factors.push((2, count_2)); n >>= count_2; } // 3 以上の奇数で試し割り let mut d = 3; while d * d <= n { if n % d == 0 { let mut count = 0; while n % d == 0 { count += 1; n /= d; } factors.push((d, count)); } d += 2; } // 残った数が 1 より大きければ、それ自体が素数 if n > 1 { factors.push((n, 1)); } factors } // Graph // Grid /* 使用例: input! { h: usize, w: usize, s: [Chars; h], } // 2次元VecをフラットにしてGrid構造体へ変換 let flattened: Vec = s.into_iter().flatten().collect(); let grid = Grid::from_vec(flattened, h, w); grid[(y, x)]でアクセスできる!! */ use std::ops::{Index, IndexMut}; #[derive(Clone, Debug)] pub struct Grid { pub height: usize, pub width: usize, pub data: Vec, } impl Grid { /// 指定されたサイズと初期値でグリッドを作成 pub fn new(height: usize, width: usize, init: T) -> Self where T: Clone, { Self { height, width, data: vec![init; height * width], } } /// 1次元のVecから作成 pub fn from_vec(data: Vec, height: usize, width: usize) -> Self { assert_eq!(height * width, data.len()); Self { height, width, data, } } /// 座標 (r, c) がグリッド内か判定 #[inline] pub fn in_bounds(&self, r: isize, c: isize) -> bool { r >= 0 && r < self.height as isize && c >= 0 && c < self.width as isize } /// 座標 (r, c) に対応する1次元インデックスを取得 #[inline] pub fn idx(&self, r: usize, c: usize) -> usize { r * self.width + c } /// 安全に要素を取得 (範囲外なら None) pub fn get(&self, r: isize, c: isize) -> Option<&T> { if self.in_bounds(r, c) { Some(&self.data[self.idx(r as usize, c as usize)]) } else { None } } /// 指定した座標の「4近傍(上下左右)」の有効な座標を列挙するイテレータを返す pub fn neighbors4(&self, r: usize, c: usize) -> impl Iterator + '_ { let dr = [0, 0, 1, -1]; let dc = [1, -1, 0, 0]; (0..4).filter_map(move |i| { let nr = r as isize + dr[i]; let nc = c as isize + dc[i]; if self.in_bounds(nr, nc) { Some((nr as usize, nc as usize)) } else { None } }) } } impl Grid { /// グリッドを文字列のベクタ (Vec) に変換して返す pub fn to_vec_string(&self) -> Vec { self.data .chunks(self.width) .map(|row| row.iter().collect()) .collect() } } // grid[(r, c)] でアクセスできるようにする impl Index<(usize, usize)> for Grid { type Output = T; fn index(&self, (r, c): (usize, usize)) -> &Self::Output { &self.data[self.idx(r, c)] } } impl IndexMut<(usize, usize)> for Grid { fn index_mut(&mut self, (r, c): (usize, usize)) -> &mut Self::Output { let idx = self.idx(r, c); &mut self.data[idx] } } // セグメントツリー用モノイド pub mod segtree_monoid { // 使用例: // let mut seg = Segtree::::from(vec![1, 2, 3]); use ac_library::{MapMonoid, Monoid}; use std::cmp::{max, min}; pub struct Min; impl Monoid for Min { type S = i64; fn identity() -> Self::S { i64::MAX } // 単位元:影響しない最大の値 fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { min(*a, *b) } } pub struct Max; impl Monoid for Max { type S = i64; fn identity() -> Self::S { i64::MIN } // 単位元:影響しない最大の値 fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { max(*a, *b) } } pub struct Sum; impl Monoid for Sum { type S = i64; fn identity() -> Self::S { 0 } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { a + b } } pub struct RangeAddMin; impl MapMonoid for RangeAddMin { type M = Min; type F = i64; fn identity_map() -> Self::F { 0 } fn mapping(f: &Self::F, x: &::S) -> ::S { if *x == i64::MAX { *x } else { x + f } } fn composition(f: &Self::F, g: &Self::F) -> Self::F { f + g } } pub struct RangeAddMax; impl MapMonoid for RangeAddMax { type M = Max; type F = i64; fn identity_map() -> Self::F { 0 } fn mapping(f: &Self::F, x: &::S) -> ::S { if *x == i64::MIN { *x } else { x + f } } fn composition(f: &Self::F, g: &Self::F) -> Self::F { f + g } } pub struct RangeUpdateMin; const NO_UPDATE_MAX: i64 = i64::MAX; impl MapMonoid for RangeUpdateMin { type M = Min; type F = i64; fn identity_map() -> Self::F { NO_UPDATE_MAX } fn mapping(f: &Self::F, x: &::S) -> ::S { if *f == NO_UPDATE_MAX { *x } else { *f } } fn composition(f: &Self::F, g: &Self::F) -> Self::F { if *f == NO_UPDATE_MAX { *g } else { *f } } } pub struct RangeUpdateMax; const NO_UPDATE_MIN: i64 = i64::MIN; impl MapMonoid for RangeUpdateMax { type M = Max; type F = i64; fn identity_map() -> Self::F { NO_UPDATE_MIN } fn mapping(f: &Self::F, x: &::S) -> ::S { if *f == NO_UPDATE_MIN { *x } else { *f } } fn composition(f: &Self::F, g: &Self::F) -> Self::F { if *f == NO_UPDATE_MIN { *g } else { *f } } } pub struct RangeSum; impl Monoid for RangeSum { type S = (i64, i64); fn identity() -> Self::S { (0, 0) } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { (a.0 + b.0, a.1 + b.1) } } pub struct RangeAddSum; impl MapMonoid for RangeAddSum { type M = RangeSum; type F = i64; fn identity_map() -> Self::F { 0 } fn mapping(f: &Self::F, x: &::S) -> ::S { (x.0 + f * x.1, x.1) } fn composition(f: &Self::F, g: &Self::F) -> Self::F { f + g } } pub struct RangeUpdateSum; const NO_UPDATE_SUM: i64 = i64::MIN; impl MapMonoid for RangeUpdateSum { type M = RangeSum; type F = i64; fn identity_map() -> Self::F { NO_UPDATE_SUM } fn mapping(f: &Self::F, x: &::S) -> ::S { if *f == NO_UPDATE_SUM { *x } else { (f * x.1, x.1) } } fn composition(f: &Self::F, g: &Self::F) -> Self::F { if *f == NO_UPDATE_SUM { *g } else { *f } } } } }