### 11375 - Matches

Posted:

**Sat Dec 29, 2007 6:26 pm**please.....give some hints ...

The UVa Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=41&t=26744

Page **1** of **2**

Posted: **Sat Dec 29, 2007 6:26 pm**

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

Posted: **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 ??

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**

answer for n=2000

Code: Select all

```
380991565762946156874961678046621248253433343260828166545367762755853547457003499038458622477079682758742141386513319975114405240307719618690948965321410900088224844552836566105758097591449004688515434992539439752768136225045759156699926199653294201865214528567739408354408370046214087724100246611181806652227233409901197263114998772667442094399468840655392398793496981172460338915324507276410832293039993597108522801725073995550343459981808085495827502753355632332659
```

Posted: **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..

Posted: **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

thank u very much

Posted: **Sat Dec 29, 2007 8:01 pm**

please !!

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

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

Posted: **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.

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**

Can anyone give more hints??

Thanks

Keep posting

Sapnil

Thanks

Keep posting

Sapnil

Posted: **Sun Dec 30, 2007 3:13 am**

Monsoon is giving a good hint how to construct a DP solution.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.

-----

Rio

Posted: **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)
Also I handle test cases for n >= 6 and add "zero" to the list of answers
I get the same answer for n = 2000 as the one posted above
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).

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
```

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
```

Code: Select all

```
2000 380991565762946156874961678046621248253433343260828166545367762755853547457003499038458622477079682758742141386513319975114405240307719618690948965321410900088224844552836566105758097591449004688515434992539439752768136225045759156699926199653294201865214528567739408354408370046214087724100246611181806652227233409901197263114998772667442094399468840655392398793496981172460338915324507276410832293039993597108522801725073995550343459981808085495827502753355632332659
```

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**

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.

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**

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**

If u are using C style char array to store the number, make sure it is terminated by '\0'Leonid wrote:The sample of my outputCode: Select all

`0 1 2 4 .......`

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**

The code is here:

http://www.stojimai.lt/problem.cpp

http://www.stojimai.lt/problem.cpp

Posted: **Mon Dec 31, 2007 12:49 am**

Ok, I just accidentially found my mistake

My code failed for the test case:

My code failed for the test case:

Code: Select all

```
6
6
```