[ZJ][數學解] a532. 奇特的數列＠Morris' Blog

2012-09-23 10:45:01| 人氣2,423| 回應0 | 上一篇 | 下一篇

[ZJ][數學解] a532. 奇特的數列

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

有一個數列的前十項：0、1、8、11、69、88、96、101、111、181，這個數列是在一次考古研究中發現，考古學家想要知道這個數列的後續發展，或許能預測人類的未來。你的任務是寫一支程式求得這個數列的任一項數值。

輸入說明：

每行一個十進位正整數Ｎ（0＜Ｎ＜＝1000000），以Ｎ＝0代表輸入結束。

輸出說明：

輸出一個非負整數，代表這個奇特數列的第Ｎ項

範例輸入：

範例輸出：

0
1
8

提示：

背景知識： DP

測資自己出的，有錯請提出><

出處：

2012成功高中校內賽第五題 (管理：eddy841021)

因為數字裡面出會出現 {0,1,6,8,9} => {0,1,2,3,4},
一樣的方法, 我們只看一半的位數, 此時要分成兩種情況討論,
長度為奇數則尾數不為 6 或 9, 因此要特別考慮, 而且 0 不能當作開頭,
那麼我們將每個一半的數字都當作一個 5 進制的數字去看, 找出 rank 之後, 再打回去對應

#include <stdio.h>
int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int dp[20] = {0,3}, x5[20] = {1}, stk[20];
    int i, j;
    char buf[5] = {'0','1','6','8','9'};
    char buf2[5] = {'0','1','9','8','6'};
    char str[30];
    for(i = 1; i < 20; i++) x5[i] = x5[i-1]*5;
    for(i = 2; i < 20; i++) {
        j = i/2;
        if(i&1)
            dp[i] = (x5[j]-x5[j-1])*3;
        else
            dp[i] = (x5[j]-x5[j-1]);
    }
    int n, l;
    while(ReadInt(&n) && n) {
        for(i = 1; i < 20; i++) {
            if(n <= dp[i]) {
                l = i;
                break;
            }
            n -= dp[i];
        }
        int idx = 0;
        j = l/2;
        if(l&1) {
            int n3 = n/3+x5[j-1]-(n%3 == 0);
            n = n - n/3*3;
            while(n3) {
                stk[idx++] = n3%5;
                n3 /= 5;
            }
        } else {
            n += x5[j-1] - 1;
            while(n) {
                stk[idx++] = n%5;
                n /= 5;
            }
        }
        int at = 0;
        for(i = j-1; i >= 0; i--)
            str[at++] = buf[stk[i]];
        if(l&1) {
            if(!n) str[at++] = '8';
            else if(n == 1) str[at++] = '0';
            else    str[at++] = '1';
        }
        for(i = 0; i < j; i++)
            str[at++] = buf2[stk[i]];
        str[at] = '\0';
        puts(str);
    }
    return 0;
}

我要檢舉

#a532#奇特的數列

台長： Morris

您可能對以下文章有興趣

a164. 區間最大連續和

d919. 最大面積

d920. 智慧盤

d633. 幼稚王國的麥田圖騰

人氣(2,423) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][dp] a449. 國王烏龜的接駁車
此分類上一篇:[ZJ] a528. 大數排序

回應(0)