10791 - Minimum Sum LCM

[ibrahim]

Some problem with your code:
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.

[midra]

thank you!
I finally got AC!

[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"

[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.

[Obaida]

Some one please help me I am getting TLE.... What's wrong with my ALGO.....

[emotional blind]

Some one please help me I am getting TLE.... What's wrong with my ALGO.....

N is large, try efficient prime factorization.

[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;
}

[Obaida]

Another thing to say How the LCM of 234 can be 24...!
Some one could explain clearly...

[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.

[Obaida]

Could you provide me some more input/output....
Like, what will be the output for 4, I found it 5.

[Jan]

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

[Obaida]

Could you tell me what will be the right algorithm...!
I couldn't find it...

[Jan]

Say, LCM(a,b) = n.
LCM(c,d) = a.
SO, LCM(c,d,b) = n.
right?

[Obaida]

At last it helped me to get Accepted !!!
Thank you brother.
Thank you again for helping me for a long time.

[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.