#include #include #include #include #include #include #include #include #include #include #include #include #include namespace lib { templateusing p_queue = std::priority_queue, Comp>; templatestruct modnum; templateconstexpr T pow(T base, std::size_t p) { if (p == 0) { return T(1); } else if (p == 1) { return base; } else if (p == 2) { return base*base; } else if (p % 2 == 0) { return pow(pow(base, p / 2), 2); } else { return pow(pow(base, p / 2), 2)*base; } } templateconstexpr auto inverse(modnum const&); templatestruct modnum { static constexpr auto mod = Mod; std::uint64_t val; modnum() = default; constexpr modnum(std::uint64_t v):val(v%Mod) { } constexpr modnum& operator+=(modnum const& v) { val += v.val; val %= mod; return *this; } constexpr modnum& operator-=(modnum const& v) { val += mod - v.val; val %= mod; return *this; } constexpr modnum& operator*=(modnum const& v) { val *= v.val; val %= mod; return *this; } constexpr modnum& operator/=(modnum const& v) { return operator*=(inverse(v)); } }; templateconstexpr auto operator+(modnum lhs, modnumconst& rhs) { return lhs += rhs; } templateconstexpr auto operator+(modnum lhs, int rhs) { return lhs += rhs; } templateconstexpr auto operator+(int lhs, modnum rhs) { return rhs += lhs; } templateconstexpr auto operator-(modnum lhs, modnumconst& rhs) { return lhs -= rhs; } templateconstexpr auto operator*(modnum lhs, modnumconst& rhs) { return lhs *= rhs; } templateconstexpr auto operator*(modnum lhs, int rhs) { return lhs *= rhs; } templateconstexpr auto operator*(int lhs, modnum rhs) { return rhs *= lhs; } templateconstexpr auto operator/(modnum lhs, modnumconst& rhs) { return lhs /= rhs; } templateconstexpr auto inverse(modnumconst& base) { return pow(base, Mod - 2); } templateconstexpr auto clamp(T v) { return std::max(v, T()); } templatevoid sort(std::vector& vec) { std::sort(vec.begin(), vec.end()); } templatevoid sort(std::vector& vec, Comp&& comp) { std::sort(vec.begin(), vec.end(), std::forward(comp)); } templatevoid vector_input(std::vector& vec) { for (auto& v : vec) { std::cin >> v; } } templateauto lower_bound(std::vectorconst& vec, T v) { return std::distance(vec.begin(), std::lower_bound(vec.begin(), vec.end(), v)); } templateauto upper_bound(std::vectorconst& vec, T v) { return std::distance(vec.begin(), std::upper_bound(vec.begin(), vec.end(), v)); } struct scope_exit { std::function func; scope_exit(std::function f):func(f) { } ~scope_exit() { func(); } }; templateusing int_tag = std::integral_constant; } void Main(); int main() { std::cin.tie(nullptr); std::cin.sync_with_stdio(false); Main(); } void Main() { int N, T; std::cin >> N >> T; std::unique_ptr memo = std::make_unique(N); for (int i{}; i < N; ++i) { for (int t{}; t <= T; ++t) { memo[i][t] = std::numeric_limits::max(); } } int beg; std::cin >> beg; memo[0][beg] = 0; for (int i = 1; i < N; ++i) { int v; std::cin >> v; for (int t{}; t <= T; ++t) { if (memo[i - 1][t] == std::numeric_limits::max()) { continue; } if (t + v <= T) { memo[i][t + v] = std::min(memo[i][t + v], memo[i - 1][t] << 1); } if (t*v <= T) { memo[i][t*v] = std::min(memo[i][t*v], (memo[i - 1][t] << 1) + 1); } } } for (int i = N - 2; i >= 0; --i) { if (memo[N - 1][T] & (1ull << i)) { std::cout << "*"; } else { std::cout << "+"; } } std::cout << std::endl; }