911 - Multinomial Coefficients

[helloneo]

Hello..~
I'm getting WA.. don't know why..
Can anybody tell me what's wrong..?
Thanks..

Code: Select all

code removed

[little joey]

I don't know. I also get WA although I think my code is correct.
For this input:

Code: Select all

10
3
4 4 2

10
4
4 3 2 1

5
5
1 1 1 1 1

100
1
101

100
1
100

100
5
90 4 3 2 1

1
1
0

1
1
1

7
7
0 0 0 0 0 0 7

I get this output:

Code: Select all

3150
12600
120
0
1
218109899151144000
0
1
1

Note that I print '0' if the exponents don't add up to n, which is correct, I think.

[Darko]

Well, someone got it accepted, so we might be missing something. I use BigInt and also print 0 if exponents don't add up to n (and they don't in some cases - unless input per test case is in more than 3 lines, I haven't considered that).

[Jan]

I have got it accepted. There can be inputs for which z1+z2+..+zk > n, then I made n = z1+z2+...+zk, and returned the result. But I think that the output should be 0.

It is not right. I have informed the judges about this problem, but they havent replied.

[Darko]

Oh, man, that's just wrong :(

Anyway - they should've tested judge's data in this volume or at least get someone to test it for them. It seems every other problem has something wrong with its I/O. And there are a few problems that shouldn't be solvable under the given constraints, but they are - those problem statements should be changed, too. (e.g n=1000000 and m <= n*(n+1)/2 ?!?)

[Jan]

I agree. The problems should be rechecked.

[helloneo]

Thanks everybody..
I got it..

[sakhassan]

Can anyone Help me ? I dont know what's worng
with this input ?

100
5
90 4 3 2 1

Code: Select all

Removed after AC

Thanks In Advance

[Jan]

I dont know what's worng
with this input ?

100
5
90 4 3 2 1

The output of your input exceeds 32 bit int. So, it is not a valid input. And you can use 'int' instead of 'double'(precision error!). Read my previous posts. I hope you will get some help.

[sakhassan]

Thanks J@N....
Really there's no such input

100
5
90 4 3 2 1

I got ma problem
I wonder if z1+z2+..+zk>n how could the output is 1 !!!!!!!!!!

[Jan]

if z1 + z2 + z3 + ... + zk > n then the output should be zero. But I believe there are no such faulty inputs(They were removed).

[farzane]

I need your help to find my mistake.I'm getting WA and realy don't know where is the bug.

Code: Select all

removed

Thanks in advance

[Jan]

Your algorithm is correct. But the problem is overflow. Check the I/O set.

Input:

Code: Select all

100
2
5 95
100
2
4 96
100
2
3 97
100
2
2 98
100
2
1 99
100
2
0 100

Output:

Code: Select all

75287520
3921225
161700
4950
100
1

Use Biginteger or use different approach. Hope these help.

[farzane]

Thank you very much jan.I got the idea,add one more function to my code and got AC.I don't know why I forget to check this case.

[sclo]

There's no need to use big integers to solve this problem. The key is to find a recurrence for the multinomial coefficient involving only sums and/or products. It is guaranteed to not overflow.