http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=704
http://codeforces.com/gym/100379

题意很简单,给你两个斐波那契进制数,求二者相加得到的斐波那契进制数。

一位一位地算,每算一位就处理一下。

附:
Zeckendorf's theorem
Fibonacci coding

/*0.028s*/

const int mx = 111;

char s1[mx], s2[mx], ans[mx];

void calc(int i)
{
    if (i == 0)
    {
        if (ans[i] == 2) ans[0] = 0, ++ans[1];
    }
    else if (ans[i - 1]) --ans[i - 1], --ans[i], ++ans[i + 1]; /// F_{n}+F{n+1}=F_{n+2}
 else if (ans[i] >= 2)
    {
        ans[i] -= 2, ++ans[i + 1];
        if (i == 1) ++ans[0];
        else ++ans[i - 2], calc(i - 2); /// 2F_{n}=F_{n+1}+F_{n-2}
 }
}

int main()
{
    int i, len1, len2, len;
    bool ok = false;
    while (gets(s1), gets(s2))
    {
        getchar();
        if (ok) putchar(10);
        else ok = true;
        len1 = strlen(s1), len2 = strlen(s2), len = max(len1, len2);
        reverse(s1, s1 + len1), reverse(s2, s2 + len2);
        mem(ans, 0);
        For(i, len)
        {
            ans[i] += (s1[i] & 15) + (s2[i] & 15);
            if (ans[i]) calc(i); /// 一位一位地算
     }
        if (ans[len]) calc(len++);
        if (ans[len]) len++; /// 这两步很重要
     rFor(i, len - 1) putchar('0' + ans[i]);
        putchar(10);
        mem(s1, 0), mem(s2, 0);
    }
    return 0;
}

Comments

comments powered by Disqus