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
编写程序,给定A0, A1 和 A2, 计算A99
Input
输入包含多行数据
每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767)
数据以EOF结束
每行数据包含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;
}