11375 - Matches

[CMG]

Did you get it accepted cause I found another similar problem. When I tested your code it gave the right output for 6, but when I tried 6 again it added one to the number like so:

Code: Select all

4
5
6
7
6
6
7

Code: Select all

4
9
16
28
17
18
29

On a off topic note, It's kinda funny that my ANSI C submission got changed to a JAVA submission . I did submit a JAVA copy but took 0.200s at lot slower than the 0.020s lol

[Leonid]

Did you get it accepted cause I found another similar problem. When I tested your code it gave the right output for 6, but when I tried 6 again it added one to the number like so:

Yes
I used global variables to store results. Before I output the answer I add 1 to global variable. Stupid me (:

[Robert Gerbicz]

you want to compute sth like this

T[n][k] = number of different numbers that can be written using exactly n matches, and if k==0 all this numbers has the most significant digit equal to 0. When k==1 is the other case.

The problem is also solvable by the simplest array:
B[n]=number of different numbers using at most n matches.
So what is asked in the problem. There is a little work how to handle the one digit solutions (also 0) in the recursion to get the correct solution.

[BUET]

I have used the following dp,

dp[n][0]->number of all numbers that can be formed by less than n matches
dp[n][1] -> number of all numbers that can be formed by using exactly n matches

dp[n][0] = dp[n-1][0] + dp[n-1][1]

dp[n][1] = dp[n-2][1] + dp[n-3][1] + dp[n-4][1] + 3*dp[n-5][1] + 2*dp[n-6] + dp[n-7]-----(i)

In the Right hand side of equation (i) for each term we have to check whether index (n-x) is 6 or not. If 6, you have to use just dp[n-x][1]-1 instead of dp[n-x][1].
if(n>13) no need to check this.
Actually this check is needed because there is a number '0' that consists of 6 matches. We can't add no more digit at the end for number 0.
dp[0][1] = 1
You have to manually generate all answers for n<=6
For each n, output dp[n][0] + dp[n][1]

Md. Shadekur Rahman
Computer Science and Engineering Department
BUET,Bangladesh