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

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

11375 - Matches

Post by Ron » Sat Dec 29, 2007 6:26 pm

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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Dec 29, 2007 6:34 pm

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
Bangladesh

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

Post by Monsoon » Sat Dec 29, 2007 6:47 pm

answer for n=2000

Code: Select all

380991565762946156874961678046621248253433343260828166545367762755853547457003499038458622477079682758742141386513319975114405240307719618690948965321410900088224844552836566105758097591449004688515434992539439752768136225045759156699926199653294201865214528567739408354408370046214087724100246611181806652227233409901197263114998772667442094399468840655392398793496981172460338915324507276410832293039993597108522801725073995550343459981808085495827502753355632332659

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Dec 29, 2007 6:54 pm

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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Dec 29, 2007 7:10 pm

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
Bangladesh

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

help....

Post by Ron » Sat Dec 29, 2007 8:01 pm

please !!

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

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

Post by Monsoon » Sat Dec 29, 2007 8:07 pm

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:

Post by sapnil » Sun Dec 30, 2007 2:37 am

Can anyone give more hints??

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

@@@ Jony @@@

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Dec 30, 2007 3:13 am

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:

Post by Leonid » Sun Dec 30, 2007 6:31 pm

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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sun Dec 30, 2007 7:12 pm

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
Bangladesh

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

Post by Leonid » Sun Dec 30, 2007 7:23 pm

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

Post by srrajesh » Sun Dec 30, 2007 7:58 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:

Post by Leonid » Mon Dec 31, 2007 12:05 am


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

Post by Leonid » Mon Dec 31, 2007 12:49 am

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

Code: Select all

6
6

Post Reply

Return to “Volume 113 (11300-11399)”