Counting

Counting

时间: 1ms        内存:64M

描述:

Gustavo knows how to count, but he is just now learning how to write numbers. He has already learned the digits 1, 2, 3, and 4. But he does not yet realize that 4 is different than 1, so he thinks that 4 is just another way to write 1.

He is having fun with a little game he created: he makes numbers with the four digits that he knows and sums their values. For example:

132 = 1 + 3 + 2 = 6

112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4 = 1)

Gustavo now wants to know how many such numbers he can create whose sum is a number n. For n = 2, he can make 5 numbers: 11, 14, 41, 44, and 2. (He knows how to count up beyond five, just not how to write it.) However, he can't figure out this sum for n greater than 2, and asks for your help.

输入:

Input will consist of an arbitrary number of integers n such that 1n1, 000. You must read until you reach the end of file.

输出:

For each integer read, output an single integer on a line stating how many numbers Gustavo can make such that the sum of their digits is equal to n.

示例输入:

2
3

示例输出:

5
13

提示:

参考答案(内存最优[1092]):

#include<stdio.h>
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
    int a[1005];
    a[1]=2;
    a[2]=5;
    a[3]=13;
    if(n>3)
    {
        int i;
        for(i=4;i<=n;i++)
        {
            a[i]=2*a[i-1]+a[i-2]+a[i-3];
        }
    }
    printf("%d\n",a[n]);
    }
    return 0;
}

参考答案(时间最优[0]):

#include<iostream>
#include<string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("5\n13\n");
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注