20111211

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]);
}

沒有留言: