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 »

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

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

Post by Kallol »

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 »

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 »

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

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

Post 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 :-)
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 »

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 »

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 »

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

Post 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

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

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

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

Post 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.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

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

Post by Leonid »

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 »

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 »


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

Post by Leonid »

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