UVa1583

題目:
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4458

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int arr[100005]; // arr[i]代表i位置的generator

    fill(arr, arr+100005, 0); // 初始化為0
    
    for(int i=1; i<100005; ++i){ // 建表
        int x = i, y = i; // x用來作為sum_of_digits，y是目前數字的copy
        while(x > 0){
            y += x%10;
            x/=10;
        }
        // 讓 y = y+sum_of_digits
        if(arr[y] == 0 || i < arr[y]) arr[y] = i; 
        // 如果arr[y] (代表y位置) 目前沒有generator(第一次被產生)，或是當前在看的generator比arr[y]還小就替換掉
        // 如果某個數字無法被產生(沒有generator)，那就不會遇到這個if case，因此不用擔心
    }

    int t, n;
    cin >> t;
    // t個case
    while(t--){
        cin >> n;
        cout << arr[n] << '\n';
        // 讀數字 直接查表給輸出
    }
    return 0;
}