11375 - Matches

[Ron]

please.....give some hints ...

[Kallol]

some tricky I/O plz ..
i am getting WA ..
i handled
input: 6
for
output : 16

what is the output for 2000 ??

[Monsoon]

answer for n=2000

Code: Select all

380991565762946156874961678046621248253433343260828166545367762755853547457003499038458622477079682758742141386513319975114405240307719618690948965321410900088224844552836566105758097591449004688515434992539439752768136225045759156699926199653294201865214528567739408354408370046214087724100246611181806652227233409901197263114998772667442094399468840655392398793496981172460338915324507276410832293039993597108522801725073995550343459981808085495827502753355632332659

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

[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

[Ron]

please !!

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

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

[sapnil]

Can anyone give more hints??

Thanks
Keep posting
Sapnil

[rio]

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

[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).

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

[Leonid]

The sample of my output

Code: Select all

0
1
2
4
9
16
28
47
80
139
30261

[srrajesh]

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.

[Leonid]

The code is here:
http://www.stojimai.lt/problem.cpp

[Leonid]

Ok, I just accidentially found my mistake
My code failed for the test case:

Code: Select all

6
6