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

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim » Mon Feb 07, 2005 11:40 pm

Some problem with your code: :o
I compare the output of your source code with my accepeted (only 0.000 seconds, rank list 1) code.
There i got so much diferants: :-?

Differenst of first 1 to 100
Comparing files MyCode.out and YourCode.OUT
***** MyCode.out
Case 17: 18
Case 18: 11
Case 19: 20
***** YourCode.OUT
Case 17: 18
Case 18: 12
Case 19: 20
*****

***** MyCode.out
Case 35: 12
Case 36: 13
Case 37: 38
***** YourCode.OUT
Case 35: 12
Case 36: 14
Case 37: 38
*****

***** MyCode.out
Case 49: 50
Case 50: 27
Case 51: 20
***** YourCode.OUT
Case 49: 50
Case 50: 28
Case 51: 20
*****

***** MyCode.out
Case 53: 54
Case 54: 29
Case 55: 16
***** YourCode.OUT
Case 53: 54
Case 54: 30
Case 55: 16
*****

***** MyCode.out
Case 71: 72
Case 72: 17
Case 73: 74
***** YourCode.OUT
Case 71: 72
Case 72: 18
Case 73: 74
*****

***** MyCode.out
Case 74: 39
Case 75: 28
Case 76: 23
***** YourCode.OUT
Case 74: 39
Case 75: 29
Case 76: 23
*****

***** MyCode.out
Case 97: 98
Case 98: 51
Case 99: 20
Case 100: 29
Case 101: 102
***** YourCode.OUT
Case 97: 98
Case 98: 52
Case 99: 20
Case 100: 30
Case 101: 102
*****

Try to solve this. :wink:

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

Post by midra » Fri Feb 11, 2005 5:21 am

thank you!
I finally got AC! :D :D :D

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Sun Feb 20, 2005 1:23 am

1. The author does NOT say about different numbers (though he speaks word "set").

2. Important:
As infinite such sequences are possible, you have to pick the sequence ...
"infinite" is the keyword. There would be finite number of such "sets" if numbers were not allowed to repeat.

P.S: And here comes word "sequence" :)
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Sun Feb 20, 2005 1:30 am

I think there must be a list of thinsgs authors must say clearly. Like this:
1. Spaces in strings - yes/no
2. Empty strings - yes/no
3. Leading zero allowed - yes/no
4. Zero is "0" (not empty string) - yes/no
5. Set is a sequence - yes/no
6. Subset/superset can be equal - yes/no
7. Any==some - yes/no
8. Multitest should be considered in asymptotic measure - yes/no
9. Expected precision - 1e-8/1e-13
10. Possibility of int64 vs. long arithmetics (when huge test is possible but avoided deliberately) - yes/no
etc...

Only 20-33% of problems don't miss a detail.
To be the best you must become the best!

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

TLE......

Post by Obaida » Wed Mar 05, 2008 6:22 am

Some one please help me I am getting TLE.... What's wrong with my ALGO.....
Last edited by Obaida on Wed Apr 09, 2008 11:40 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: TLE......

Post by emotional blind » Fri Mar 07, 2008 6:07 pm

Obaida wrote:Some one please help me I am getting TLE.... What's wrong with my ALGO.....
N is large, try efficient prime factorization.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10791

Post by Obaida » Wed Apr 09, 2008 11:42 am

But Now I am getting WA... So many as well.... :(

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
	long long int n,i,c=0;
	while(scanf("%lld",&n)==1&&n!=0)
	{
		c++;
		i=2;
		int k=1;
		long long int sum=0,count=1;
		if(n==1)printf("Case %lld: 2\n",c);
		else
		{
			while(n!=1&&k!=0)
			{
				if(n%i==0)
				{
					sum=sum+i;
					n=n/i;
					count=0;
				}
				else
					i++;
				if(i>sqrt(n))
				{
					k=0;
					sum=sum+n;
					break;
				}
			}
			if(count==1)printf("Case %lld: %lld\n",c,sum+1);
			else printf("Case %lld: %lld\n",c,sum);
		}
	}
	return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10791

Post by Obaida » Wed Apr 09, 2008 12:00 pm

Another thing to say How the LCM of 234 can be 24...!
Some one could explain clearly...
try_try_try_try_&&&_try@try.com
This may be the address of success.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10791

Post by Jan » Thu Apr 10, 2008 12:52 am

Code: Select all

lcm(2,9,13) = 234 and sum(2,9,13) = 24
And you can't get any result less than 24. So, 24 is the correct answer for 234. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10791 - Minimum Sum LCM

Post by Obaida » Thu Apr 10, 2008 7:17 am

Could you provide me some more input/output....
Like, what will be the output for 4, I found it 5.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10791 - Minimum Sum LCM

Post by Jan » Fri Apr 11, 2008 12:25 am

Your code fails on 234. And I think your algorithm is not right. However, the result for 4 is 5.
Ami ekhono shopno dekhi...
HomePage

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10791 - Minimum Sum LCM

Post by Obaida » Tue Apr 29, 2008 12:30 pm

Could you tell me what will be the right algorithm...!
I couldn't find it...
try_try_try_try_&&&_try@try.com
This may be the address of success.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10791 - Minimum Sum LCM

Post by Jan » Wed Apr 30, 2008 3:15 pm

Say, LCM(a,b) = n.
LCM(c,d) = a.
SO, LCM(c,d,b) = n.
right?
Ami ekhono shopno dekhi...
HomePage

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10791 - Minimum Sum LCM

Post by Obaida » Thu May 22, 2008 2:12 pm

At last it helped me to get Accepted :) !!!
Thank you brother.
Thank you again for helping me for a long time.
try_try_try_try_&&&_try@try.com
This may be the address of success.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10791 - Minimum Sum LCM

Post by DD » Tue Mar 29, 2011 6:42 am

If you still got W.A., just try 2147483647. The answer is 2147483648. I forgot the internal implicit type conversion such that I got 2 W.As even I used long long int. :cry:
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 107 (10700-10799)”