10721 - Bar Codes

[schindlersp]

I need input critical and outpu correct please.

my teste ==>

7 4 2
7 4 3
14 7 4
50 20 25
50 5 4

my output ==>

4
16
603
2017909539
0





Thanks Schindler

[Krzysztof Duleba]

Output:

4
16
1128
18851684047504
0

[schindlersp]

Thanks ...

I'm search my mistake ..

Schindler

[muvee]

I get Right answers for sample input as well as the input provided in another thread.. Anyone who has an ACC program, please try this input for me:

Code: Select all

7 4 2
7 4 3
14 7 4
50 50 50
16 5 4
14 9 8
13 9 25
40 4 2
2 4 50
50 25 1
23 27 10
49 1 18
30 30 30
30 15 40
30 20 10

My output is:

Code: Select all

4
16
1128
1
65
1287
495
0
0
0
0
0
1
77558760
20029990

Thanks in advance![/quote]

[Krzysztof Duleba]

Your output is correct. Check for boundary cases. Do you use 64-bit integers?

[muvee]

Thanks for your reply. Yes I am using 64 bit integers and the way I've done it, overflow is impossible. Can you give me some boundary conditions?

[Krzysztof Duleba]

Try this:

Input:

50 5 4
50 5 4
4 5 3
4 5 8
5 4 8
5 4 1
5 4 2
5 4 50
1 1 1
1 1 2
50 20 19

Output:

0
0
0
4
0
4
4
1
1
18850592351584

[muvee]

I think you left out one zero at the beginning.. this is what I am getting :

Code: Select all

0
0
0
0
4
0
4
4
1
1
18850592351584

Just a quick question. When you are calculating a value for e.g. 32!/(4!5!)
do you simply calculate num and den and then return num/den... I am doing it by expanding num and expanding den and then simplifying until I have 1 in the den. I did this to make sure I didn't get any overflow. Have you also done it this way?

Thanks.

[Krzysztof Duleba]

I think you left out one zero at the beginning

Sorry, somehow I doubled the first line while copy-pasting the input.

When you are calculating a value for e.g. 32!/(4!5!)
do you simply calculate num and den and then return num/den...
I am doing it by expanding num and expanding den and then simplifying until I have 1 in the den.
I did this to make sure I didn't get any overflow. Have you also done it this way

I usually do it your way, but here I went for memorization with + as the only operation.

Here you have all the bounary conditions that I check in my code.
Input:

1 2 5
-1 2 1
2 -6 5
10 10 100
10 10 2
5 1 3
5 1 6
5 1 5

Output:

0
0
0
1
1
0
1
1

[muvee]

Here's my last throw of the dice!! Please give me your output for this sample input :

5 22 50
39 10 18
7 13 19
11 38 12
19 36 15
41 15 26
27 27 50
16 39 2
5 39 12
40 49 30
4 25 24
12 49 47
27 21 2
50 4 33
28 32 42
50 50 24
7 11 37
30 37 32
50 13 39
38 34 14
50 50 50
1 1 1
50 1 1
1 50 1
1 1 50
50 50 1
50 1 50
1 50 50
5 22 50
39 10 18
7 13 19
11 38 12
19 36 15
41 15 26
27 27 50
16 39 2
5 39 12
40 49 30
4 25 24
12 49 47
27 21 2
50 4 33
28 32 42
50 50 24
7 11 37
30 37 32
50 13 39
38 34 14
21 21 18
45 39 40
32 7 15
30 2 39
28 28 42
39 15 32
37 22 32
20 24 20
23 38 23
42 32 21

My output :

0
163481480
0
0
0
23206929825
1
0
0
0
0
0
54264
18732
0
1
0
0
92389469380
66045
1
1
0
0
1
1
1
0
0
163481480
0
0
0
23206929825
1
0
0
0
0
0
54264
18732
0
1
0
0
92389469380
66045
1
7059052
796376
30
1
9669554100
5567902560
0
0
1121099408

[muvee]

In your last post, some of your cases had negative number in them but the problem states that

Each input will contain three positive integers n, k, and m (1 ≤ n, k, m ≤ 50).

So I don't think those are valid inputs. Apart from those, mine did match yours.

[Krzysztof Duleba]

I know that there should be no negative input, but I don't trust OJ at all Anyway, the problem is somewhere else as my output is different:

0
161332040
0
0
0
23206929825
1
0
0
0
0
0
54264
16184
0
1
0
0
92263734836
66045
1
1
0
0
1
1
1
0
0
161332040
0
0
0
23206929825
1
0
0
0
0
0
54264
16184
0
1
0
0
92263734836
66045
1
7059052
680225
29
1
9669554100
5567902560
0
0
1121099408

[muvee]

I had made a dumb mistake. I fixed that and now ALL our outputs are matching except one. But I am not sure if yours is right or mine.

The case is : 30 2 39

I get the following combinations from my program:

1 29 --> 2 combos (1 29 and 29 1)
2 28 --> 2
3 27 --> 2
4 26 --> 2
5 25 --> 2
6 24 --> 2
7 23 --> 2
8 22 --> 2
9 21 --> 2
10 20 --> 2
11 19 --> 2
12 18 --> 2
13 17 --> 2
14 16 --> 2
15 15 --> 1


So shouldn't the answer be (14x2) +1 = 29 rather than 30.

[Krzysztof Duleba]

And 29 it is

[muvee]

Hahaha... This problem is affecting my eyesight now ... so basically ALL our outputs match. Part of the problem is that I am running this on VC++ 6.0 using __int64 .. when I submit it to the judge I change it to long long int and make the relevant changes in the printf... but I never get to actually see the results of it using long long int ... Oh well.. I'm satisfied with my solution!

Could you please let me know your method of calculating N!/(H!J!) ... Because my solution is giving WA after 5 seconds and I see that many people are getting ACC in less than 0.5 sec.

And thanks for all your help.