| Counting |
Gustavo knows how to count, but he is now learning how write numbers. As he is a very good student, he already learned 1, 2, 3 and 4. But he didn‘t realize yet that 4 is different than 1, so he thinks that 4 is another way to write 1. Besides that, he is having fun with a little game he created himself: he make numbers (with those four digits) and sum their values. For instance:
132 = 1 + 3 + 2 = 6 112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4 = 1)After making a lot of numbers in this way, Gustavo now wants to know how much numbers he can create such that their sum is a number n. For instance, for n = 2 he noticed that he can make 5 numbers: 11, 14, 41, 44 and 2 (he knows how to count them up, but he doesn‘t know how to write five). However, he can‘t figure it out for n greater than 2. So, he asked you to help him.
Input will consist on an arbitrary number of sets. Each set will consist on an integer n such that 1 <= n <= 1000. You must read until you reach the end of file.
For each number read, you must output another number (on a line alone) stating how much numbers Gustavo can make such that the sum of their digits is equal to the given number.
2 3
5 13
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<string> v;
string add(string a, string b)
{
string s;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int i = 0;
int m, k = 0;
while(a[i] && b[i])
{
m = a[i] - '0' + b[i] - '0' + k;
k = m / 10;
s += (m % 10 + '0');
i++;
}
if(i == a.size())
{
while(i != b.size())
{
m = k + b[i] - '0';
k = m / 10;
s += m % 10 + '0';
i++;
}
if(k) s += k + '0';
}
else if(i == b.size())
{
while(i != a.size())
{
m = k + a[i] - '0';
k = m / 10;
s += m % 10 + '0';
i++;
}
if(k) s += k + '0';
}
reverse(s.begin(), s.end());
return s;
}
void solve()
{
v.push_back("0");
v.push_back("2");
v.push_back("5");
v.push_back("13");
string s;
for(int i = 4; ; i++)
{
s = add(v[i-1], v[i-1]);
s = add(v[i-2], s);
s = add(v[i-3], s);
v.push_back(s);
if(v[i].size() > 1001) break;
}
}
int main()
{
solve();
int n;
int Size = v.size();
while(cin >> n)
{
cout << v[n] << endl;
}
return 0;
}版权声明：本文博主原创文章，博客，未经同意不得转载。
原文：http://www.cnblogs.com/hrhguanli/p/4855393.html