package main import ( "fmt" "strings" ) func main() { var N, TOTAL int var A []int fmt.Scan(&N, &TOTAL) A = make([]int, N) for i := 0; i < N; i++ { fmt.Scan(&A[i]) } fmt.Println(solve(N, TOTAL, A)) } func solve(N, total int, A []int) string { dp := make([]map[int]bool, N) for i := 0; i < N; i++ { dp[i] = make(map[int]bool) } dp[0][A[0]] = true dp[len(dp)-1][total] = true backcast(dp, A) return forcast(dp, A) } func backcast(dp []map[int]bool, A []int) { for i := len(dp) - 1; i > 0; i-- { dpn := dp[i-1] a := A[i] for b := range dp[i] { if b > a { dpn[b-a] = true } if b%a == 0 { dpn[b/a] = true } } } } func forcast(dp []map[int]bool, A []int) string { pos := 1 val := A[0] path := make([]string, 0, len(dp)-1) dfs(val, pos, &path, dp, A) return strings.Join(path, "") } func dfs(val int, pos int, path *[]string, dp []map[int]bool, A []int) bool { if pos == len(dp) { return true } a := A[pos] if _, ok := dp[pos][val+a]; ok { *path = append(*path, "+") if dfs(val+a, pos+1, path, dp, A) { return true } *path = (*path)[:len(*path)-1] } if _, ok := dp[pos][val*a]; ok { *path = append(*path, "*") if dfs(val*a, pos+1, path, dp, A) { return true } *path = (*path)[:len(*path)-1] } return false }