11375 - Matches

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG » Mon Dec 31, 2007 12:55 am

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 :o. I did submit a JAVA copy but took 0.200s at lot slower than the 0.020s lol
Last edited by CMG on Mon Dec 31, 2007 1:03 am, edited 1 time in total.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Post by Leonid » Mon Dec 31, 2007 1:02 am

CMG wrote: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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Mon Dec 31, 2007 4:36 pm

Monsoon wrote: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
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

11375 - Matches

Post by BUET » Sun Aug 19, 2012 4:02 pm

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

Post Reply

Return to “Volume 113 (11300-11399)”