10198 - Counting
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1139
The Problem
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.
The Input
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.
The Output
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.
Sample Input
2
3
Sample Output
5
13
思路:用f[i]表示n=i时的答案,则考虑末位数字,如果选择1的话,那么一共有f[i-1]个数,如果是2的话,一共有f[i-2]个数,3有f[i-3]个数,4有f[i-1]个数。
所以:f[i]=2*f[i-1]+f[i-2]+f[i-3]
完整代码:
/*0.014s*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 410;
char numstr[maxn];
struct bign
{
int len, s[maxn];
bign()
{
memset(s, 0, sizeof(s));
len = 1;
}
bign(int num)
{
*this = num;
}
bign(const char* num)
{
*this = num;
}
bign operator = (const int num)
{
char s[maxn];
sprintf(s, "%d", num);
*this = s;
return *this;
}
bign operator = (const char* num)
{
len = strlen(num);
for (int i = 0; i < len; i++) s[i] = num[len - i - 1] & 15;
return *this;
}
///输出
const char* str() const
{
if (len)
{
for (int i = 0; i < len; i++)
numstr[i] = '0' + s[len - i - 1];
numstr[len] = '\0';
}
else strcpy(numstr, "0");
return numstr;
}
///去前导零
void clean()
{
while (len > 1 && !s[len - 1]) len--;
}
///加
bign operator + (const bign& b) const
{
bign c;
c.len = 0;
for (int i = 0, g = 0; g || i < max(len, b.len); i++)
{
int x = g;
if (i < len) x += s[i];
if (i < b.len) x += b.s[i];
c.s[c.len++] = x % 10;
g = x / 10;
}
return c;
}
///减
bign operator - (const bign& b) const
{
bign c;
c.len = 0;
for (int i = 0, g = 0; i < len; i++)
{
int x = s[i] - g;
if (i < b.len) x -= b.s[i];
if (x >= 0) g = 0;
else
{
g = 1;
x += 10;
}
c.s[c.len++] = x;
}
c.clean();
return c;
}
///乘
bign operator * (const bign& b) const
{
bign c;
c.len = len + b.len;
for (int i = 0; i < len; i++)
for (int j = 0; j < b.len; j++)
c.s[i + j] += s[i] * b.s[j];
for (int i = 0; i < c.len - 1; i++)
{
c.s[i + 1] += c.s[i] / 10;
c.s[i] %= 10;
}
c.clean();
return c;
}
///除
bign operator / (const bign &b) const
{
bign ret, cur = 0;
ret.len = len;
for (int i = len - 1; i >= 0; i--)
{
cur = cur * 10;
cur.s[0] = s[i];
while (cur >= b)
{
cur -= b;
ret.s[i]++;
}
}
ret.clean();
return ret;
}
///模、余
bign operator % (const bign &b) const
{
bign c = *this / b;
return *this - c * b;
}
bool operator < (const bign& b) const
{
if (len != b.len) return len < b.len;
for (int i = len - 1; i >= 0; i--)
if (s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
bool operator > (const bign& b) const
{
return b < *this;
}
bool operator <= (const bign& b) const
{
return !(b < *this);
}
bool operator >= (const bign &b) const
{
return !(*this < b);
}
bool operator == (const bign& b) const
{
return !(b < *this) && !(*this < b);
}
bool operator != (const bign &a) const
{
return *this > a || *this < a;
}
bign operator += (const bign &a)
{
*this = *this + a;
return *this;
}
bign operator -= (const bign &a)
{
*this = *this - a;
return *this;
}
bign operator *= (const bign &a)
{
*this = *this * a;
return *this;
}
bign operator /= (const bign &a)
{
*this = *this / a;
return *this;
}
bign operator %= (const bign &a)
{
*this = *this % a;
return *this;
}
} f[1005];
int main(void)
{
f[1] = 1, f[2] = 5, f[3] = 13;
for (int i = 4; i <= 1000; ++i)
f[i] = f[i - 1] + f[i - 1] + f[i - 2] + f[i - 3] ;
int n;
while (scanf("%d", &n))
puts(f[n].str());
return 0;
}
分享到:
相关推荐
To reflect that, and to make the Counting Practices Manual (CPM) even more attractive as a reference manual, the Counting Practices Committee (CPC) decided to restructure CPM 4.2 into four parts: ...
The Function Point Counting Practices Manual is the definitive description of the Function Pointing Counting Standard. Several versions of the manual are available, each describing the standard or ...
Function Point Counting Practices Manual (功能点计算实践手册)4.3版
The Pleasures of Counting 1996 © Cambridge University Press 1996
These practices are a compilation of acceptable proce- dures for cycle-counting methods employed in fatigue analysis. This standard does not intend to recommend a particular method.
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
1004. Counting Leaves (30) 来自:http://blog.csdn.net/sunbaigui/article/details/8657008
GRE 数学-Magoosh Probability & Counting+解析1
Function Point Counting Practices Manual 4.1.1 版本。 来自IFPUG,权威资料 The primary objectives of the IFPUG Counting Practices Manual, Release 4.1, are to • Provide a clear and detailed description...
Counting源代码统计器,对开发的代码进行统计,辅助开发者进行开发,也可以用于软件测试时对代码的统计
可以统计source有效行,空行,注释行,文件的大小,统计的文件数目的工具
To reflect that, and to make the Counting Practices Manual (CPM) even more attractive as a reference manual, the Counting Practices Committee (CPC) decided to restructure CPM 4.2 into four parts: ...
论文Attentional Neural Fields for Crowd Counting,侵删
Zhang_Cross-Scene_Crowd_Counting_2015_CVPR_paper.pdf
输出一段字串中的字符数——程序很小,第一次上传,大家多支持!
统计代码量的工具 软件开发必备 简单易操作
3D人员计数例程系统文档
利用差分盒计数法计算图像分维数,利用matlab语言编写
Give "1 Jan 1900 was a Monday", get "How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
一个统计代码行的很简单很适用的小工具-a statistical line of code is very simple and very applicable to the small tools