uva10198,

# Problem E: Counting

## 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.

```2
3```

```5
13```

## Solution:

Deal with big number is much difficulty if using C++.
The code is copied from Blog Link.
The copyright is reserved by the owner of that blog.

## Source Code:

//Wed Mar 30 12:31:14 CDT 2011
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

BigInteger dp[] = new BigInteger[1000 + 10];

Arrays.fill(dp, BigInteger.ZERO);

dp[0] = BigInteger.valueOf(1);
dp[1] = BigInteger.valueOf(2);
dp[2] = BigInteger.valueOf(5);
dp[3] = BigInteger.valueOf(13);

for (int i = 4; i <= 1000; i++) {
dp[i] = dp[i].add(dp[i - 1]);
dp[i] = dp[i].add(dp[i - 2]);
dp[i] = dp[i].add(dp[i - 3]);
dp[i] = dp[i].add(dp[i - 1]);
}

int n;

while (input.hasNextInt()) {
n = input.nextInt();
System.out.println(dp[n]);
}
}
}
The text passage describes a problem where Gustavo, who only knows the digits 1, 2, 3, and 4 (and considers 4 as 1), wants to count how many numbers he can create such that the sum of their digits equals a given number n. The passage includes a sample input and output, and a solution in Java.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
uva10198,

# Problem E: Counting

## 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.

```2
3```

```5
13```

## Solution:

Deal with big number is much difficulty if using C++.
The code is copied from Blog Link.
The copyright is reserved by the owner of that blog.

## Source Code:

//Wed Mar 30 12:31:14 CDT 2011
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

BigInteger dp[] = new BigInteger[1000 + 10];

Arrays.fill(dp, BigInteger.ZERO);

dp[0] = BigInteger.valueOf(1);
dp[1] = BigInteger.valueOf(2);
dp[2] = BigInteger.valueOf(5);
dp[3] = BigInteger.valueOf(13);

for (int i = 4; i <= 1000; i++) {
dp[i] = dp[i].add(dp[i - 1]);
dp[i] = dp[i].add(dp[i - 2]);
dp[i] = dp[i].add(dp[i - 3]);
dp[i] = dp[i].add(dp[i - 1]);
}

int n;

while (input.hasNextInt()) {
n = input.nextInt();
System.out.println(dp[n]);
}
}
}
user
The text passage describes a problem where Gustavo, who only knows the digits 1, 2, 3, and 4 (and considers 4 as 1), wants to count how many numbers he can create such that the sum of their digits equals a given number n. The passage includes a sample input and output, and a solution in Java.

TYPE: SINGLE_QUESTION_WITH_ANSWER