切換
舊版
前往
大廳
主題

ZeroJudge - e558: 01583 - Digit Generator 解題心得

Not In My Back Yard | 2019-12-09 22:44:55 | 巴幣 0 | 人氣 276

題目連結:


題目大意:
在此我們定義正整數 N 的「位數和」(並稱此數為 M)為其自身以及其每位數之值總和,且將 N 稱作為 M 的「生成數」。例如 245 的位數和為 245 + 2 + 4 + 5 = 256 ,因此 245 是 256 的生成數。

有的數有多個生成數,例如 216 有 198 和 207 兩個生成數;有的數則沒有任何生成數,例如 121 。

給定一正整數 T ,代表有 T 筆測試資料,每筆佔一列。每列給定一正整數 N (1 ≦ N ≦ 100000),求 N 最小的生成數為何?如果 N 沒有任何生成數,請輸出「0」。



範例輸入:
3
216
121
2005


範例輸出:
198
0
1979


解題思維:
因為位數和必定大於原本的數。因此,我們可以宣告一個陣列(每個位置初始化為 0),並從 N = 100000 開始往下跑。每跑一個數字,便求該數字的位數和 M ,並將陣列的第 M 個位置所儲存的值更新為現在跑到的 N 值。

當以上跑完之後,陣列裡每個位置儲存的數字便是該位置最小的生成數(如果值為 0 ,代表沒有生成數)。因為 N 由大到小,因此 N 的位數和也會越來越小。所以導致以上的結果。

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

創作回應

更多創作