use std::{ collections::{BTreeSet, HashMap, HashSet, VecDeque}, fmt::Debug, io::stdin, str::FromStr, sync::OnceLock, }; use proconio::marker::Chars; fn main() { proconio::input! { n: u32, t: u32, a: [u32; n], } let result = f(a[0], t, &mut Vec::new(), &a[1..], &mut HashSet::new()).unwrap(); let result = result .into_iter() .map(|o| match o { Op::Plus => '+', Op::Mult => '*', }) .collect::(); println!("{result}"); } #[derive(Debug, Clone, Copy)] enum Op { Plus, Mult, } fn f( v: u32, t: u32, op: &mut Vec, a: &[u32], memo: &mut HashSet<(u32, usize)>, ) -> Option> { if a.is_empty() { return (v == t).then(|| op.clone()); } if memo.contains(&(v, a.len())) { return None; } if v < t { op.push(Op::Plus); let plus_v = v + a[0]; if let Some(r) = f(plus_v, t, op, &a[1..], memo) { return Some(r); } op.pop(); op.push(Op::Mult); let mult_v = v * a[0]; if let Some(r) = f(mult_v, t, op, &a[1..], memo) { return Some(r); } op.pop(); } memo.insert((v, a.len())); None }