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

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Output when N=1

Post by erdos » Sun Dec 12, 2004 9:52 pm

I got lots of wrong answers in this problem when n=1.
(I was answering 0 and in a later submission 1)

I think n=1 shouldn't be a valid input. (altough in description it's stated as that).

When n=1 there aren't 2 integers which lcm gives 1.

I just saw in this board that when n=1, output should be 2.
(1*1 = 1 , 1+1=2)...
But I don't think the output should be 2. It doesn't make sense... (since {1,1} is not a set).

Any comments on this ?

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

Post by Adrian Kuegel » Sun Dec 12, 2004 10:32 pm

Since the problemsetter decided that 1 is a valid input, we have to produce an output that is expected for that. And the output 2 is far more logical than 0 or 1, although you can argue that {1,1} is no set.

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by erdos » Sun Dec 12, 2004 11:23 pm

Precisely because {1,1} is no set I can not see the logic of 2 being the answer.
The problem description requires the numbers to sum to be different.

What arguments do you have for 2 being a better answer than 0 ?
0 seems the best answer since there's no solution. (no set, so the sum is 0)

Anyway, I think the problem should be revised to exclude 1 from being a valid input.

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

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

Sure, theoretically there is no solution. But why should 0 indicate the value of no solution? You have arbitrarily chosen 0.
Since the problemsetter didn't define anything that should indicate a "no solution", we have to assume he thinks there is always a solution. Now, 2 makes more sense as output for 1, since if we assume the problemsetter thought of a multiset when he wrote his problem description, this would be the output.
I don't want to say that 2 is the correct output for 1, I only tried to show how you can find a way to get accepted systematically in cases where the problemsetter made a mistake.
And in my opinion, the description should only change set to multiset, then everything is ok.

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by erdos » Mon Dec 13, 2004 12:23 am

A multiset is a set where elements can be repeated ?
If so the algorithm to solve would be different. (would be trivial, that way)

The problem makes sense as it is. (with a set...but without 1 as a valid input I think ;-)

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

Post by Adrian Kuegel » Mon Dec 13, 2004 12:31 am

You are right, it wouldn't be the same problem. Sorry.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon Dec 13, 2004 1:04 am

Why would the problem be different if multiset were used instead of set for N > 1?

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

Post by Adrian Kuegel » Mon Dec 13, 2004 1:13 am

When I wrote my last post, I thought that then the rule to use at least 2 numbers would be meaningless. In fact, it is not, since using a number twice would make the sum bigger than using 1 instead. So probably multiset wouldn't change the problem, but it would make 1 a valid input.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Dec 13, 2004 11:46 pm

By that interpretation, wouldn't it make more sense for the answer of "1" to be "3"?

lcm( 1, 2 ) = 1..

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

Post by Adrian Kuegel » Mon Dec 13, 2004 11:51 pm

How is lcm(1,2) = 1?
1 is no multiple of 2, right?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Dec 14, 2004 2:30 am

Sorry, was thinking of GCD for some odd reason.. :D

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

10791. Why WA ???

Post by midra » Sun Jan 02, 2005 2:04 am

I really can't understand what's wrong with my code...
I think I take care of everything, but I still got WA
here is my code:

Code: Select all

#include <stdio.h>

unsigned long res=0;

calc(unsigned long n){
    int i,j,sum=1;
    while(n%2==0){
        n=n/2;
        sum*=2;
    }
    if (sum>1){
         res+=sum;
         sum=1;
    }    
    i=3;
    while(i*i<=n){
        while(n%i==0){
            n=n/i;
            sum*=i;
        }
        if(sum>1) {
           res+=sum;
           sum=1;
        }    
      i+=2;
    }
    res+=n;
    if(res==n) 
       return 0;
    return 1;
      
}    

int main()
{
  unsigned long n;
  int c=0;
  while(scanf("%lu",&n)&n!=0){
      c++;
      if(calc(n))
        printf("Case %d: %lu\n",c,res);
      else
        printf("Case %d: %lu\n",c,n+1);        
     res=0;
  }    
  return 0;
}
thanks to everyone!

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Jan 02, 2005 8:59 am

On few trials, I couldn't spot any wrong output. But I am not sure about the algorithm you used, could you describe it.

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post by prince56k » Sun Jan 02, 2005 10:28 am

input:
100
200
300

output:
Case 1: 29
Case 2: 33
Case 3: 32

Hope it helps

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra » Tue Feb 01, 2005 7:01 am

first of all
I am so sorry...for the waiting
shamim:
the algorithm just take the input number, it factorize in primes, and for every prime it factorize it sums to the result...I mean for example
24=2^3 * 3
so there are three 2's so one of the numbers that must stay is 8 because the LCM are the common and not common factors of all the numbers
and the other is the 3
another example
1575: 3^2 * 5^2 * 7
so the numbers that have to appear to form 1575 as LCM are {9, 25,7}
so the sum must be 41
sorry but my english is so bad so it is difficult to explain what I think in english...
Now I have no time, but tomorrow I would make a better explanation of this just to the people that want some help with this problem

prince56k:
Thank you so much for this great help, tomorrow I will debug my code so it works fine...
byee and sorry again for the waiting!

Post Reply

Return to “Volume 107 (10700-10799)”