主題

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

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

題目連結：

題目大意：

在此我們定義正整數 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」。

範例輸入：

216

121

2005

範例輸出：

198

1979

解題思維：

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

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

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

ETH官方钱包