poj_3982_ProblemD_序列.cpp

Problem Links:

poj3982,

Problem:

序列

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3612		Accepted: 1571

Description

数列A满足An = An-1 + An-2 + An-3, n >= 3

编写程序，给定A0, A1 和 A2, 计算A99

Input

输入包含多行数据

每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767)
数据以EOF结束

Output

对于输入的每一行输出A99的值

Sample Input

1 1 1

Sample Output

69087442470169316923566147

Source

Solution:

Use string instead of the long long. The system won't allocate that much memory for it.

Source Code:

//Tue Nov 23 14:30:01 CST 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

string add(string A, string B)
{
    int sz = max(A.size(), B.size());
    int flag = 0;
    if(sz > (int)A.size()) A += string(sz-A.size(), '0');
    if(sz > (int)B.size()) B += string(sz-B.size(), '0');
    string ret = "";
    for(int i=0; i<sz; i++)
    {
        int temp = A[i]-'0' + B[i] - '0' + flag;
        flag = temp > 9 ? 1 : 0;
        temp %= 10;
        ret += ('0' + temp);
    }
    if(flag == 1)
        ret += ('0' + flag);
//  cout << A << ", " << B << ", " << ret << endl;
    return ret;
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
    string a0, a1, a2;
    while (cin >> a0 >> a1 >> a2)
    {
        vector<string> ret(100, "");
        reverse(a0.begin(), a0.end());
        reverse(a1.begin(), a1.end());
        reverse(a2.begin(), a2.end());
        ret[0] = a0;
        ret[1] = a1;
        ret[2] = a2;
        for (int i = 3; i < 100; i++)
        {
            ret[i] = add(ret[i - 1], add(ret[i - 2], ret[i - 3]));
        }
        reverse(ret[99].begin(), ret[99].end());
        cout << ret[99] << endl;
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}