10042 - Smith Numbers

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

zprian
New poster
Posts: 13
Joined: Wed Mar 09, 2005 1:16 am

Post by zprian » Thu Mar 24, 2005 12:20 am

HI WR!! I OBTAINED AN ACCEPT!!!jejeje
I change the loop, and I check each number and use long, and now my program is ACCEPT!!!
thanks very much for all!!!

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

ACC 10042 ..At last

Post by Rocky » Mon Mar 28, 2005 11:26 am

Thanks For I/O
I Got ACC Now.I forgot To Post

Thank's

Rocky
:)

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

10042

Post by asif_rahman0 » Wed Jun 01, 2005 7:51 pm

Hello can anybody plz help me to understand the problem 10042? :roll:

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Wed Jun 01, 2005 8:21 pm

At first make sure what a smith number is. By definition - Smith number is such a number that the sum of its digits is equal to the sum of digits of all it's prime factors (considering frequency). Let's consider the example given in the problem.
4937775 can be written as 3 * 5 * 5 * 65837 - which are it's prime factors.
Now, if you sum the digits of the original number, you get (4 + 9 + 3 + 7 + 7 + 7 + 5) = 42. Again summing the digits of the prime factors leads to -> {(3) + (5) + (5) + (6 + 5 + 8 + 3 + 7)} = 42. As both the sums are equal, 4937775 is a smith number.

Now, if you check the sample input, you will find 4937774 is not a smith number. Increment the number by one until you get a smith number which is the immediate next one in this case.

Similarly, if the input is 105, it's not a smith number and 106,107,108....,120 - none of these are smith #. The first smith # after 105 is 121. This will be your output. Hope it helps. :)
You should never take more than you give in the circle of life.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Thanks

Post by asif_rahman0 » Thu Jun 02, 2005 2:55 am

Thanks Mahmudur Bhai for your help.I now understand the problem and get ready for code.

Pasa Yildirim
New poster
Posts: 14
Joined: Mon Mar 07, 2005 7:10 pm
Location: Bosnia and Herzegovina
Contact:

10042 WA

Post by Pasa Yildirim » Tue Nov 22, 2005 8:53 pm

Hello!

I have problems with my program :). Can anybody tell me what's wrong in the code. I use algorithm from Programming Challenges.

Code: Select all

// 10042: Smith numbers

#include <cmath>
#include <iostream>
using namespace std;

typedef unsigned long inte;

inte sum (inte n)
{
	inte r = 0;	
	while (n)
	{
		r += n % 10;
		n /= 10;
	}
	return 0;
}

// This algorithm is from Programming challenges, 
// it works for me in other ACM problems
inte ptr (inte w)
{
	inte n = w;
	inte rez = 0;
	
	while (n % 2 == 0)
	{
		rez += 2;
		n /= 2;
	}
	
	inte i = 3;
	while (i <= (sqrt(n) + 1))
	{
		if (n % i == 0)
		{
			rez += sum(i);
			n /= i;
		}
		else i += 2;
	}
	
	if (n > 1) rez += sum(n);
	
	// If n == w ==> n is prime 
	if (n == w) return false;
	
	if (sum(w) == rez) return true;
	return false;
}

int main (void)
{	
	inte t; cin >> t;
	
	while (t--)
	{
		inte n; cin >> n;
		while (!ptr(++n));
		cout << n << endl;
	}
	
//	system("pause");
	return 0;
}


chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Wed Nov 23, 2005 5:14 am

You made a very careless mistake in your code. I refer you to this part of your code:

Code: Select all

inte sum (inte n) 
{ 
   inte r = 0;    
   while (n) 
   { 
      r += n % 10; 
      n /= 10; 
   } 
   return 0; 
} 
This sum function is always returning 0. I think you meant return r.

Pasa Yildirim
New poster
Posts: 14
Joined: Mon Mar 07, 2005 7:10 pm
Location: Bosnia and Herzegovina
Contact:

Post by Pasa Yildirim » Wed Nov 23, 2005 8:46 pm

chunyi81, thank you very much, i've got AC.
I don't even think that my mistake is so obivious :) :)
Thank you once more ;)

Masud
New poster
Posts: 5
Joined: Sat May 06, 2006 1:12 am
Location: Bangladesh
Contact:

10042

Post by Masud » Sat May 06, 2006 2:27 am


I dont know why judge give me wrong answer
My code is given below...
What is the problem of it...

Code: Select all

#include<stdio.h>
#include<math.h>


long long int DigSum(long long int t)
{
 long long int m=0;
 while(t)
	{
     m+=t%10;
	 t/=10;
	}
 return m;
}

long long int PrimeFactorSum(long long int t)
{
 long long int k=0,i,d;
 while(t%2==0)
	{
	 k+=2;
	 t/=2;
	}
  d=sqrt(t);
 for(i=3;i<=d;i+=2)
	{
	 if(t%i==0)
		{
		 while(t%i==0)
			{
			k+=DigSum(i); 
			t/=i;
			}
		 d=sqrt(t);
		}
	}
 if(t>=i)k+=DigSum(t);
 return k;
}



void main()
{
 long cas;
 long long int sum1,sum2,n;
 scanf("%ld",&cas);
 while(cas--)
	{
	 scanf("%lld",&n);
	 while(0==0)
		{
		 sum1=DigSum(n);
	     sum2=PrimeFactorSum(n);
		 if(sum1==sum2)break;
	     else n++;
		}
	 printf("%lld\n",n);

	}
}
Hi I am Masud...

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sat May 06, 2006 10:27 am

Read the question carefully
For every input value n, you are to compute the smallest Smith number which is larger than n.
...prime number is not worth being a Smith number...
Always search the forum for existing threads about your topic and use them if necessary instead of creating a new one. I'm sure you'll find a lot more help along with some test I/O if you search.

rieo
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain

about SIGSEGV

Post by rieo » Tue Jul 04, 2006 11:22 am

hi,

in 10042 smith numbers, i try the all input from other topic and get correct answer use gcc.

but when i submit my code, it gets signal 11 (SIGSEGV). Meaning:
Invalid memory reference

but i don't know in what condition could make this mistake


is there anyone can help me? thx.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Tue Jul 04, 2006 1:36 pm

It is possibly because of your program tried to access the invalid memory, for example if you write the code like this :

Code: Select all

int arr[1000];
arr[1001] = 5;
printf("%d\n",arr[1001]);
It might be error, because you made an array with capacity only 1000 but you tried to access the 1002nd array... (0 is the 1st array).

rieo
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain

Post by rieo » Tue Jul 04, 2006 11:06 pm

if my array is : int prime[20000]; and i write a function
int digitsum(unsigned long int a)

then i write
psum+=digitsum(prime);
could make SIGSEGV ?

or unsigned long int s
but s=s%prime or s/=prime
could make SIGSEGV ?

because i test all data from 0 - 10^9 in gcc and all answer is fine

but when i submit... get SIGSEGV

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Wed Jul 05, 2006 7:20 am

Maybe its time you posted the code in its entirety.
--
Suman
My Blog
My Web Page

rieo
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain

Post by rieo » Wed Jul 05, 2006 1:54 pm

finally i get accept, i found the bug is i use store primes which are <100000
, and when i test the input s, and use s to mod by prime.. if use all the primes < 100000, s still can't be 1, i wrote if (s>prime[10000]) digitsum(s)
and get RE

when i change the code to if (s!=1) the digitsum(s) directly... it's accept

thx your reply

Post Reply

Return to “Volume 100 (10000-10099)”