876 . 運算的可能性

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

coding_pooh

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

60.0% (6/10)

Tags

ntucpc-speedrun1

Description

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

給定一個序列 a1,a2,…,aN，序列中相鄰數字對共會形成 N−1 個空白位，請試圖在每個空白位填入 +、- 或著不填，進而使運算結果得到 X。其中不填的意義即為串接相鄰兩個數字。

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

Input Format

首行輸入兩個整數 N,X 代表序列的長度以及欲計算得出的目標，次行 N 個正整數 a1,a2,…,aN，代表序列的內容。

  • 1≤N≤14
  • −1015≤X≤1015
  • 1≤ai≤99
  • 保證不存在兩組解答可以在運算後得到 X。

Output Format

若任何的填入方式都無法使運算結果為 X，輸出 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
Submit
Back to Top