10791 - Minimum Sum LCM

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

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10791 - Minimum Sum LCM

Post by htl » Sun Dec 12, 2004 11:20 am

How about the following in/output?

in:
2342
2343
34
1
234
678
67223
76627567
334
787890
787611
0

out:
Case 1: 1173
Case 2: 104
Case 3: 19
Case 4: 2
Case 5: 31
Case 6: 119
Case 7: 5184
Case 8: 22408
Case 9: 169
Case 10: 131321
Case 11: 23900


Could someone give some critical case?

totster
New poster
Posts: 4
Joined: Sun Dec 12, 2004 12:28 pm

Post by totster » Sun Dec 12, 2004 12:32 pm

htl wrote: in:
2342
2343
34
1
234
678
67223
76627567
334
787890
787611
0

out:
Case 1: 1173
Case 2: 104
Case 3: 19
Case 4: 2
Case 5: 31
Case 6: 119
Case 7: 5184
Case 8: 22408
Case 9: 169
Case 10: 131321
Case 11: 23900
I get:

Case 1: 1173
Case 2: 85
Case 3: 19
Case 4: 2
Case 5: 24
Case 6: 118
Case 7: 5184
Case 8: 4829
Case 9: 169
Case 10: 26273
Case 11: 866

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Sun Dec 12, 2004 1:32 pm

I think I could understand your algorithm. But what's wrong with my program? Any critical case could cause error?

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Sun Dec 12, 2004 2:01 pm

I think you misunderstand the problem. The problem description reads:
a set of AT LEAST two positive integers

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Sun Dec 12, 2004 2:13 pm

I have modified my code that I get the same answer as above. But I still got WA. I don't know what I haven't paid attention to.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Dec 12, 2004 5:25 pm

You have to use unsigned int for the result, since input can be: 2^31 - 1, so output is 2^31.
Last edited by Adrian Kuegel on Sun Dec 12, 2004 6:22 pm, edited 1 time in total.

unknown_error
New poster
Posts: 5
Joined: Fri Dec 10, 2004 9:42 am

Post by unknown_error » Sun Dec 12, 2004 6:17 pm

for input 2^31-1 the output is 2^31. so, it's better to use unsigned int or long long .. for this silly mistake i needed 5 submission during the contest to get AC :lol:

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Dec 12, 2004 6:22 pm

Sure, output is 2^31 in that case. Sorry for my typo.

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Sun Dec 12, 2004 7:39 pm

hi totster.
should the answer of 234 be 21.
you have write for 234 , 24
atleat i can say that 234=2*3*3*13,then sum =21.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Dec 12, 2004 7:54 pm

But lcm of 2,3,3,13 is 78, so your result is wrong.

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Sun Dec 12, 2004 8:09 pm

what abt 4
4 = 4,since 2*2=4 but lcm of 2,2=2;//corrcted
or 4 = 5, 4*1=4,4+1=5
Last edited by harry on Sun Dec 12, 2004 8:15 pm, edited 1 time in total.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Dec 12, 2004 8:11 pm

Sure, for 4 the output should be 5.
Last edited by Adrian Kuegel on Sun Dec 12, 2004 8:18 pm, edited 1 time in total.

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Sun Dec 12, 2004 8:12 pm

now i am a bit confused.how can i get solution for such input.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Dec 12, 2004 8:17 pm

The idea is basically very simple. Say, the factorization of n is p1^q1 * p2^q2 * ... * pk^qk. Clearly, each pi^qi has to be a divisor of one of the numbers, otherwise the lcm of the numbers is not n. So in case of n = 4, the factorization is 2^2, so 4 has to be a divisor of one number. Now, since this specifies only one number, you have to add another one, and you have only the choice between 1,2 and 4. Clearly, 1 is the best choice (and it always is, if you have only one prime factor).

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Sun Dec 12, 2004 8:24 pm

thanks adrian . i was thinking in a wrong way.i forgot to consider
"Clearly, each pi^qi has to be a divisor of one of the numbers"

Post Reply

Return to “Volume 107 (10700-10799)”