ACM 443 Humble Numbers

ACM136進階版。
不能直接output了，囧。

第一次嘗試用DP解題目，似乎也沒這麼難，
不過要想得到算法。
主要的想法參考於這裡！
真是好厲害！

humble number = (2 ^ w) * (3 ^ x) * (5 ^ y) * (7 ^ z)
用DP的想法是，一開始只有1，1會變成2 3 5 7，
而2 3 5 7各自再乘上2 3 5 7後共有16種組合，
但是沒這麼多，因為有重複的情況。
前項的結果再乘上2 3 5 7，必定也是humble number，
（偉哉DP，好強大）
再繼續深入思考，
若一開始只有1，乘上2 3 5 7之後，取其中最小的一個數值。
這個情況下是2，這樣的話，下次質數2就是從第二個humble number開始乘(即2 * 2），
3 5 7還是要乘第一個質數(即3 * 1 5 * 1 7 * 1)，
接著四個數值繼續做比大小的動作（4 3 5 7相比），
這個情況下是3，所以下次質數3要從第二個humble number開始乘(即3 * 2）
也就是說，每次取完最小的值，
下次該質數就要從下一個humble number做相乘的動作，
因為上一個humble number已經乘完啦！
但還沒結束，還要考慮humble number相同的情況，
例如3 * 5或5 * 3，是一樣的，
所以如果一樣，就必須把3跟5的紀錄次數各 + 1，
意即，每次找到最小值之後，只要是2 3 5 7的乘積與此值相等，
就各要 + 1。

最後要注意ordinal number，以前英文沒學好，-_-，傻傻搞不清楚。
只要十位數是1，都是加th，（不管個位數是不是1 2 3）
其他的情況下，1 2 3分別加st nd rd，
其餘都是th。

/* ACM 443 Humble Numbers
 * mythnc
 * 2011/12/11 21:49:31   
 * run time: 0.012
 */
#include <stdio.h>
#include <string.h>

#define MAXN 5842

void precal(int *);
void output(int, int *);

int main(void)
{
    int ans[MAXN];
    int n;

    precal(ans);

    while (scanf("%d", &n) && n != 0)
        output(n, ans);

    return 0;
}

/* precal: previous calculation the answer */
void precal(int *ans)
{
    int t2, t3, t5, t7;
    int p2, p3, p5, p7, count;

    p2 = p3 = p5 = p7 = 0;
    ans[0] = count = 1;
    while (count < MAXN) {
        t2 = ans[p2] * 2;
        t3 = ans[p3] * 3;
        t5 = ans[p5] * 5;
        t7 = ans[p7] * 7;
        /* find the minimal */
        if (t2 <= t3 && t2 <= t5 && t2 <= t7)
            ans[count] = t2;
        else if (t3 < t2 && t3 <= t5 && t3 <= t7)
            ans[count] = t3;
        else if (t5 < t2 && t5 < t3 && t5 <= t7)
            ans[count] = t5;
        else if (t7 < t2 && t7 < t3 && t7 < t5)
            ans[count] = t7;
        /* if same, prime number have to move to next */
        if (t2 == ans[count])
            p2++;
        if (t3 == ans[count])
            p3++;
        if (t5 == ans[count])
            p5++;
        if (t7 == ans[count])
            p7++;

        count++;
    }
}

/* output: print out the answer in the format */
void output(int n, int *ans)
{
    char number[3];

    if (n % 100 < 10 || n % 100 > 20)
        switch (n % 10) {
            case 1:
                strcpy(number, "st");
                break;
            case 2:
                strcpy(number, "nd");
                break;
            case 3:
                strcpy(number, "rd");
                break;
            default:
                strcpy(number, "th");
        }
    else
        strcpy(number, "th");

    printf("The %d%s humble number is %d.\n", n, number, ans[n - 1]);
}