HDOJ-1058 丑数

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1058

序数词太ex了...

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
mt19937_64 rng(random_device{}());
string get_suf(int x) {
    if (x / 10 % 10 == 1) return "th";
    if (x % 10 == 1) return "st";
    if (x % 10 == 2) return "nd";
    if (x % 10 == 3) return "rd";
    return "th";
}
void solve() {
    vector<int> dp(N, INT_MAX);
    dp[1] = 1;
    int cur[4] = {1, 1, 1, 1};
    int base[4] = {2, 3, 5, 7};
    for (int i = 2; i <= 5842; ++i) {
        vector<int> vec(4);
        for (int j = 0; j < 4; ++j) {
            vec[j] = dp[cur[j]] * base[j];
        }
        dp[i] = *min_element(vec.begin(), vec.end());
        for (int j = 0; j < 4; ++j) {
            if (dp[i] == dp[cur[j]] * base[j]) ++cur[j];
        }
    }
    int n;
    while (cin >> n && n) {
        cout << "The " << n << get_suf(n) << " humble number is " << dp[n] << ".\n";
    }
}
int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T;
    // cin >> T;
    // while (T--) 
        solve();
    return 0;
}