UVA1583 - Digit Generator

UVA1583 - Digit Generator

四月 05, 2019

題目簡述

一個數加上他的各位數稱爲他的 digitSum
若 a 的 digitSum 爲 b，則稱 a 爲 b 的 digitGenerator
e.g. 123+1+2+3 = 129，則123是129的 digitGenerator
給定一正整數 n，求 n 最小的 digitGenerator，若無則輸出 0

初步想法

digitGenerator 一定小於他所生成的值，暴力破解即可得解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* UVA1583 - Digit Generator
 * Author: ifTNT
 * Total time complexity: O(n*t)
 */

#include <iostream>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i=1; i<=n; i++){
            int sum=i;
            int tmp=i;
            while(tmp!=0){
                sum += tmp%10;
                tmp /= 10;
            }
            if(sum==n){
                cout << i << endl;
                break;
            }
            if(i==n){
                cout << "0" << endl;
                break;
            }
        }
    }
    return 0;
}

還能更快嗎

  1. 題目測資範圍爲1~100000，表示 digitGenerator 小於5位數，考慮 digitGenerator 每位都是9的情況，則 n 和 digitGenerator 最多差 5*9=45 因此可以將迴圈範圍改寫成 [n-45, n]，以縮小範圍。
  2. 若測資筆數大於 100000//45=2222 筆的話，先建表再直接查表會更有經濟效率。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /* UVA1583 - Digit Generator
     * Author: ifTNT
     * Total time complexity: O(t)
     * Space used: 10^5
     */

    #include <iostream>
    using namespace std;

    int main(){
        //initial table
        int digitGenerator[100001];
        for(int i=0; i<=100000; i++){
            digitGenerator[i]=0;
        }
        for(int i=0; i<=100000; i++){
            int sum=i;
            int tmp=i;
            while(tmp!=0){
                sum += tmp%10;
                tmp /= 10;
            }
            if(digitGenerator[sum]==0){
                digitGenerator[sum]=i;
            }

        }

        int t;
        cin >> t;
        while(t--){
            int n;
            cin >> n;
            cout << digitGenerator[n] << endl;
        }
        return 0;
    }