Page 1 of 2

11375 - Matches

Posted: Sat Dec 29, 2007 6:26 pm
by Ron
please.....give some hints ...

Posted: Sat Dec 29, 2007 6:34 pm
by Kallol
some tricky I/O plz ..
i am getting WA ..
i handled
input: 6
for
output : 16

what is the output for 2000 ??

Posted: Sat Dec 29, 2007 6:47 pm
by Monsoon
answer for n=2000

Code: Select all

380991565762946156874961678046621248253433343260828166545367762755853547457003499038458622477079682758742141386513319975114405240307719618690948965321410900088224844552836566105758097591449004688515434992539439752768136225045759156699926199653294201865214528567739408354408370046214087724100246611181806652227233409901197263114998772667442094399468840655392398793496981172460338915324507276410832293039993597108522801725073995550343459981808085495827502753355632332659

Posted: Sat Dec 29, 2007 6:54 pm
by Observer
Even though I generated the judge input, I am not aware of any special cases... Ah maybe N = 1. Not very tricky but well.. :D

Posted: Sat Dec 29, 2007 7:10 pm
by Kallol
thanks for ur output , monsoon ... as usual I did a stupid mistake not counting that additional number for making '0' with 6 sticks , for all n>=6.
thank u very much :-)

help....

Posted: Sat Dec 29, 2007 8:01 pm
by Ron
please !!

give me hint to solve this problem.....................

Posted: Sat Dec 29, 2007 8:07 pm
by Monsoon
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.

Posted: Sun Dec 30, 2007 2:37 am
by sapnil
Can anyone give more hints??

Thanks
Keep posting
Sapnil

Posted: Sun Dec 30, 2007 3:13 am
by rio
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.
Monsoon is giving a good hint how to construct a DP solution.
-----
Rio

Posted: Sun Dec 30, 2007 6:31 pm
by Leonid
I'm getting mad at myself.
I handle test cases for n < 6 well:
(The first number on a line is just for conveniece, I don't print it in the real answer)

Code: Select all

1 0
2 1
3 2
4 4
5 9
Also I handle test cases for n >= 6 and add "zero" to the list of answers

Code: Select all

6 16
7 28
8 47
9 80
10 139
20 30261
30 6604100
40 1441129285
50 314479087270
60 68624723704732
70 14975090230202473
80 3267821206355634204
90 713094563875592361477
100 155609448901280828126891
I get the same answer for n = 2000 as the one posted above

Code: Select all

2000 380991565762946156874961678046621248253433343260828166545367762755853547457003499038458622477079682758742141386513319975114405240307719618690948965321410900088224844552836566105758097591449004688515434992539439752768136225045759156699926199653294201865214528567739408354408370046214087724100246611181806652227233409901197263114998772667442094399468840655392398793496981172460338915324507276410832293039993597108522801725073995550343459981808085495827502753355632332659
Also I've tried to compile my code with g++ and VC++ where I get the same answer
Since answer for n = 2000 in my code depends on previous answers I can't imagine the kind of special test case where I'd get WA, but still WA - I'm getting crazy :(
Any ideas?

I use Windows on my PC, and the judge uses Linux. Maybe there is a problem with my BigInteger class on Linux machine or some other part of my code (once I had rounding problem on Linux, while solution on Windows worked fine).

Posted: Sun Dec 30, 2007 7:12 pm
by Kallol
using windows or Linux should not be the issue here ..
ur outputs match with outputs of my AC code ...
I think there may be any mistake in ur output formatting ..
If u show how u printed the answer , I think the reason can be revealed.

Posted: Sun Dec 30, 2007 7:23 pm
by Leonid
The sample of my output

Code: Select all

0
1
2
4
9
16
28
47
80
139
30261

Posted: Sun Dec 30, 2007 7:58 pm
by srrajesh
Leonid wrote:The sample of my output

Code: Select all

0
1
2
4
.......
If u are using C style char array to store the number, make sure it is terminated by '\0'
I remeber doing such silly mistake in some other problem, which prevented me from getting AC

Better post the code, so that we could try to spot the bug.

Posted: Mon Dec 31, 2007 12:05 am
by Leonid

Posted: Mon Dec 31, 2007 12:49 am
by Leonid
Ok, I just accidentially found my mistake :)
My code failed for the test case:

Code: Select all

6
6