前往
大廳
主題

ZeroJudge - c423: pB 還原密碼 解題心得

Not In My Back Yard | 2021-06-20 00:00:09 | 巴幣 10 | 人氣 228

題目連結:


題目大意:
輸入第一列給定兩正整數 N 、 R (3 ≦ N ≦ 30,0 ≦ R ≦ 9),代表密碼為 N 位數且密碼的根為 R 。接下來的一列給定 N - 1 位數的數字(數字皆介於 0 ~ 9 之間),代表密碼的一部分。

一個數字的根為:將其各個位數之數值相加,得一新數。重複此步驟直到最後的數字只有一位數,此時該數字即為「根」。

因此我們可以從 N - 1 位數得出可能的 N 位數字(根據根之值 R),但是已知所有可能數字中的最小值以及最大值不會是密碼(其他的才是可能的密碼)。由小到大輸出所有可能的密碼(可以假設至少有一組可能的密碼)。



範例輸入:
輸入範例 1:
3 6
12

輸入範例 2:
4 5
138

輸入範例 3:
5 4
0011


範例輸出:
輸出範例 1:
132

輸出範例 2:
1328
1382

輸出範例 3:
00121
00211
02011


解題思維:
要快速求得一個數字的「根」可以利用這題的想法。

剩下的就是直接窮舉看看哪些數字(0 ~ 9)可以加進去 N - 1 位數數字中。對於每個可行數字再窮舉所有可以插入的位置(注意窮舉出來的數字可能重複)。

將所有可能的數字去除掉最小值以及最大值,剩下的即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作