-
Notifications
You must be signed in to change notification settings - Fork 1
/
1793.cpp
47 lines (44 loc) · 952 Bytes
/
1793.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<string>
using namespace std;
string rev(string str)
{
string r = "";
int len1 = str.length();
for (int i = len1 - 1; i >= 0; i--)
r += str[i];
return r;
}
string add(string str1, string str2)
{
string ans = "";
int len1 = str1.length() - 1;
int len2 = str2.length() - 1;
int temp, carry = 0;
while (true)
{
if (len1 >= 0 && len2 >= 0) temp = (str1[len1--] - '0') + (str2[len2--] - '0') + carry;
else if (len1 < 0 && len2 >= 0) temp = (str2[len2--] - '0') + carry;
else if (len2 < 0 && len1 >= 0) temp = (str1[len1--] - '0') + carry;
else break;
if (temp > 9)
{
carry = 1;
temp -= 10;
}
else carry = 0;
ans += (temp + '0');
}
if (carry) ans += (carry + '0');
return rev(ans);
}
int main()
{
string ans[255] = { "1", "1", "3" };
for (int i = 3; i <= 251; i++)
ans[i] = add(ans[i - 1], add(ans[i - 2], ans[i - 2]));
int n;
while (cin >> n)
cout << ans[n] << endl;
return 0;
}