10721 - Bar Codes

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

schindlersp
New poster
Posts: 28
Joined: Tue Aug 03, 2004 8:11 pm
Contact:

10721 - Bar Codes

Post by schindlersp » Tue Oct 12, 2004 11:11 pm

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Oct 13, 2004 1:16 am

Output:
4
16
1128
18851684047504
0

schindlersp
New poster
Posts: 28
Joined: Tue Aug 03, 2004 8:11 pm
Contact:

10721

Post by schindlersp » Wed Oct 13, 2004 7:04 am

Thanks ...

I'm search my mistake ..

Schindler

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

10721 Output Required

Post by muvee » Mon Nov 01, 2004 3:13 am

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]
Last edited by muvee on Mon Nov 01, 2004 6:10 pm, edited 1 time in total.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Nov 01, 2004 4:56 am

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

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Mon Nov 01, 2004 2:41 pm

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?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Nov 01, 2004 4:27 pm

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
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Mon Nov 01, 2004 7:03 pm

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Nov 01, 2004 8:54 pm

muvee wrote:I think you left out one zero at the beginning
Sorry, somehow I doubled the first line while copy-pasting the input.
muvee wrote: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
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Mon Nov 01, 2004 9:50 pm

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
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Mon Nov 01, 2004 9:52 pm

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Nov 01, 2004 10:58 pm

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
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Mon Nov 01, 2004 11:29 pm

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Nov 01, 2004 11:37 pm

And 29 it is :-)

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Mon Nov 01, 2004 11:59 pm

Hahaha... This problem is affecting my eyesight now :o ... 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.

Post Reply

Return to “Volume 107 (10700-10799)”