N,T,*A = $<.read.split.map &:to_i debug = false h = {} s = ?+*(N - 1) def succ s if s[-1] == ?+ s[0..-2] + ?* else succ(s[0..-2]) + ?+ end end def culc a, s l = a.size-1 sum = a[0] l.times{|i| case s[i] when ?+ then sum+=a[i+1] when ?* then sum*=a[i+1] end } sum end loop{ c = culc A, s p [:top, s, h, c] if debug #### break if c == T if c > T last_asterisk_index = s=~/\*[^*]*$/ if A[last_asterisk_index + 1] > 1 s = succ(s[0, last_asterisk_index + 1]) + ?+*(N - last_asterisk_index - 2) next end end b = (2..N).each{|j| partial_sum = culc(A[0, j], s[0, j - 1]) if h[[j, partial_sum]] p [:before, s, j] if debug #### s = succ(s[0, j - 1]) + ?+*(N - j) p [:after, s, j] if debug #### break end } if s[-1] == ?* s[/\*+$/].size.times{|k| 2 + 1 + 1 * 1 * 8 partial_sum = culc(A[0, N - k - 1], s[0, N - k - 2]) p [:centre_before, s, k, h] if debug #### h[[N - k - 1, partial_sum]] = partial_sum p [:centre_after, s, k, h] if debug #### } end s = succ s if b } p s, h if debug $><