## 11375 - Matches

Moderator: Board moderators

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### 11375 - Matches

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
some tricky I/O plz ..
i am getting WA ..
i handled
input: 6
for
output : 16

what is the output for 2000 ??
Last edited by Kallol on Sat Dec 29, 2007 7:08 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Code: Select all

``````380991565762946156874961678046621248253433343260828166545367762755853547457003499038458622477079682758742141386513319975114405240307719618690948965321410900088224844552836566105758097591449004688515434992539439752768136225045759156699926199653294201865214528567739408354408370046214087724100246611181806652227233409901197263114998772667442094399468840655392398793496981172460338915324507276410832293039993597108522801725073995550343459981808085495827502753355632332659
``````

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Even though I generated the judge input, I am not aware of any special cases... Ah maybe N = 1. Not very tricky but well..
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### help....

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

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
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
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Can anyone give more hints??

Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:
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
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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.
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:
The sample of my output

Code: Select all

``````0
1
2
4
9
16
28
47
80
139
30261``````

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm
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.

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

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:
Ok, I just accidentially found my mistake
My code failed for the test case:

Code: Select all

``````6
6``````