回分類題庫
e026: 2.還原密碼
關鍵字: 104學年度全國決賽

測資點 : 4 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 34 Times / 33 Users | Submit : 230 Times / 52 Users | Accepted rate : 63%
題目加入時間 : 2016-11-17 13:46

Content: 简体中文

蓋茲是一位著名的寶藏獵人,他花了兩年的時間追尋一批從漢朝流傳下來的寶藏。去年他在西安郊區的寺廟中得到一條線索,包含一段文字「數字加總,反覆為之,止於一位,謂之為根。」以及一個數字 5。今年他又在洛陽的石窟裡找到另一段文字「增添一位,其根相符,不為最大,不為最小。」和一組數字 138。上個月他找到跟這批寶藏有關的寶藏盒,可是寶藏盒還需要兩組四個數字的密碼才能打開。

他思考了很久,總算參透了這兩條線索的意思。

第一條線索所說的,是把一組數字的每個數字加總起來,反覆操作,直到變成一位數字,稱之為根。例如數字 138 會變成 1+3+8=12 再變成 1+2=3,3 便稱為 138 的根。

第二條線索所說的,是要把 138 加上一位數字,讓此組數字的根為第一條線索說的 5。符合根為 5 的數字組合有四個,分別是 2138,1238,1328 和 1382。不是最大也不是最小的組合是 1328 和 1382,蓋茲嘗試了這兩組密碼,果然就打開了寶藏盒。

現在要請你寫一個程式進行類似上述的密碼還原工作。 

Input:

輸入的第一行有一個整數 T,代表接下來有幾筆測試資料。 

每筆測試資料有兩行,第一行有兩個整數值,以一個空白字元隔開。第一個整數 N (3 <= N <= 30) 代表密碼有幾個數字。第二個數為根 R (0 <= R <= 9)。 

第二行有連續 (N-1) 個數字 d1d2d3…d(N-1),數字 di 屬於{0, 1, 2, …, 9},(1 <= i <= N–1)。 

Output:

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

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
3 6
12
4 5
138
5 4
0011

Sample Output :

132
1328
1382
00121
00211
02011

Hint :

Author :

104學年度全國決賽 (管理員:sagit)

  Solve it!   Status Forum