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

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

Post by ibrahim »

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 »

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 »

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 »

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 »

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.

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

Re: TLE......

Post by emotional blind »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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)”