TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

93.5% (29/31)

Submission's AC Ratio

29.8% (36/121)

Description

蓋茲是一位著名的寶藏獵人,他花了兩年的時間追尋一批從漢朝流傳下來的寶藏。
去年他在西安郊區的寺廟中得到一條線索,包含一段文字「數字加總,反覆為之,止於一位,謂之為根。」以及一個數字5。今年他又在洛陽的石窟裡找到另一段文字「增添一位,其根相符,不為最大,不為最小。」和一組數字138。上個月他找到跟這批寶藏有關的寶藏盒,可是寶藏盒還需要兩組四個數字的密碼才能打開。
他思考了很久,總算參透了這兩條線索的意思。
第一條線索所說的,是把一組數字的每個數字加總起來,反覆操作,直到變成一位數字,稱之為根。例如數字138 會變成1+3+8=12 再變成1+2=3,3 便稱為138 的根。
第二條線索所說的,是要把138 加上一位數字,讓此組數字的根為第一條線索說的5。符合根為5 的數字組合有四個,分別是2138,1238,1328 和1382。不是最大也不是最小的組合是1328 和1382,蓋茲嘗試了這兩組密碼,果然就打開了寶藏盒。
現在要請你寫一個程式進行類似上述的密碼還原工作。

Input Format

每筆測資有兩行。
第一行有兩個整數值,以一個空白字元隔開。第一個整數N (3 ≤ N ≤ 30) 代表密碼有幾個數字。第二個數為根 R (0 ≤ R ≤ 9)。
第二行有連續 (N-1) 個數字d1d2d3…d(N-1),數字di∈{0, 1, 2, …, 9},(1 ≤ i ≤ N–1)。

Output Format

依據輸入,由小到大輸出所有可能的密碼,每組密碼輸出於獨立的一行。(可假設至少有一組可能的密碼。)

Sample Input

輸入範例1:
3 6
12

輸入範例2:
4 5
138

輸入範例3:
5 4
0011

Sample Output

輸出範例1:
132

輸出範例2:
1328
1382

輸出範例3:
00121
00211
02011

Hints

本題共有三組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組10 分,所有的測資3 ≤ N ≤ 5,且輸入和輸出都不會有數字0。
第二組20 分,所有的測資3 ≤ N ≤ 5。
第三組70 分,所有的測資3 ≤ N ≤ 30。

Problem Source

104學年度高級中學資訊學科能力競賽決賽程式設計試題第二題
Set by Paupière

Subtasks

For Testdata: 0 ~ 4, Score: 10
For Testdata: 5 ~ 9, Score: 20
For Testdata: 10 ~ 14, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 65536
1 1000 131072 65536
2 1000 131072 65536
3 1000 131072 65536
4 1000 131072 65536
5 1000 131072 65536
6 1000 131072 65536
7 1000 131072 65536
8 1000 131072 65536
9 1000 131072 65536
10 1000 131072 65536
11 1000 131072 65536
12 1000 131072 65536
13 1000 131072 65536
14 1000 131072 65536