TopCoder

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

57.1% (4/7)

Tags

Description

你是否有想過數字的運算結果能有多豐富?有一個坊間著名的問題是這樣的:

給定一個序列 $a_1, a_2, \ldots, a_N$,序列中相鄰數字對共會形成 $N-1$ 個空白位,請試圖在每個空白位填入 $\texttt{+}$、$\texttt{-}$ 或著不填,進而使運算結果得到 $X$。其中不填的意義即為串接相鄰兩個數字。

舉例來說,若輸入的數字是 $1\ 2\ 3\ 4$,而填入的符號分別是「$\texttt{+}$、不填、$\texttt{-}$」的話,就會得到運算式 $1+23-4=20$,會是 $X=20$ 的一組解;若輸入的數字是 $3\ 1\ 4\ 1\ 5$,而填入的符號分別是「不填、不填、$\texttt{+}$、$\texttt{-}$」的話,就會得到運算式 $314+1-5$,會是 $X=310$ 的一組解。

Input Format

首行輸入兩個整數 $N, X$ 代表序列的長度以及欲計算得出的目標,次行 $N$ 個正整數 $a_1, a_2, \ldots, a_N$,代表序列的內容。

  • $1\leq N \leq 14$
  • $-10^ {15}\leq X \leq 10^ {15}$
  • $1\leq a_i \leq 99$
  • 保證不存在兩組解答可以在運算後得到 $X$。

Output Format

若任何的填入方式都無法使運算結果為 $X$,輸出 $\texttt{Not Found}$,否則,輸出運算式的長相,詳細格式可以參考範例輸出。

Sample Input 1

4 20
1 2 3 4

Sample Output 1

1+23-4

Sample Input 2

5 310
3 1 4 1 5

Sample Output 2

314+1-5

Sample Input 3

4 3
2 6 8 6

Sample Output 3

Not Found

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~18 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2