640  Self Numbers
Moderator: Board moderators
Hi all !
I wrote a program, which solvs the problem, but runing sth about 50 sec on my computer !!! How to make it faster ?
[cpp]
#include <iostream>
#include <conio.h>
using namespace std;
int sum_of_digits(long n)
{
long k,power;
int sum;
for (power=1;;power*=10)
{
if (n/power==0) break;
}
power/=10;
for (k=power;k>1;k/=10)
{
sum+=n/k;
n%=k;
}
sum+=n;
return sum;
}
int isself(long l)
{
long j,temp;
for (j=l1;;j)
{
temp=sum_of_digits(j);
if (temp+j==l) return 0;
if (temp+j<l) return 1;
}
}
int main()
{
for (long i=1;i<=1000000;)
{
if (isself(i)==1)
{
cout << i << endl;
}
if (i+2%2!=0)
{
if (isself(i+2)==1) i+=2; else i+=11;
}
else i+=11;
}
return 0;
}
[/cpp]
I wrote a program, which solvs the problem, but runing sth about 50 sec on my computer !!! How to make it faster ?
[cpp]
#include <iostream>
#include <conio.h>
using namespace std;
int sum_of_digits(long n)
{
long k,power;
int sum;
for (power=1;;power*=10)
{
if (n/power==0) break;
}
power/=10;
for (k=power;k>1;k/=10)
{
sum+=n/k;
n%=k;
}
sum+=n;
return sum;
}
int isself(long l)
{
long j,temp;
for (j=l1;;j)
{
temp=sum_of_digits(j);
if (temp+j==l) return 0;
if (temp+j<l) return 1;
}
}
int main()
{
for (long i=1;i<=1000000;)
{
if (isself(i)==1)
{
cout << i << endl;
}
if (i+2%2!=0)
{
if (isself(i+2)==1) i+=2; else i+=11;
}
else i+=11;
}
return 0;
}
[/cpp]
It isn't possible to solve this in 0.000 at all. The time I have is the result of the glitch in the system some two years ago. Else I would have time around 0.0100.020. That is a possible time. With good IO and a trick to generation of the numbers.
Cheers,
Ivor
Cheers,
Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

 Learning poster
 Posts: 57
 Joined: Fri Oct 10, 2003 11:01 pm
 Location: in front of PC
 Contact:
Faster I/O please
How can I generate FASTER I/O
Mine is 0:00.391
Mine is 0:00.391
There are two tragedies in life one is to lose your hearts' desire and another is to gain it  GBS.

 New poster
 Posts: 12
 Joined: Mon Mar 28, 2005 7:55 pm
 Contact:
A better approach could be to first precalculate all selfnumbers
from 1 to 1000000 using a technique similar to the
Eratosthenes Sieve ( although the logical checks in the algorithm
and actually the whole logic are quite different ).
Then, as a second step, you just loop and print the selfnumbers.
Please let me know if you need more details.
P.A.Petrov ( Sedefcho )
from 1 to 1000000 using a technique similar to the
Eratosthenes Sieve ( although the logical checks in the algorithm
and actually the whole logic are quite different ).
Then, as a second step, you just loop and print the selfnumbers.
Please let me know if you need more details.
P.A.Petrov ( Sedefcho )

 New poster
 Posts: 12
 Joined: Mon Mar 28, 2005 7:55 pm
 Contact:

 Learning poster
 Posts: 63
 Joined: Tue Sep 20, 2005 12:31 am
 Location: Dhaka
 Contact:
640 TLE
Hi All.............................
Plz tell me efficient Algorithm.
I got TLE.
Here is my code:
Pls help me!!!!!!!
Thanks in advence!!!
Plz tell me efficient Algorithm.
I got TLE.
Here is my code:
Code: Select all
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 1000000
char table[MAX+2];
long long sumdigit(long long n)
{
long long sum = 0;
while(n>0)
{
sum+=(n%10);
n/=10;
}
return sum;
}
void unself(long long n)
{
long long i, sum;
i = n;
while(i<=MAX)
{
sum = sumdigit(i);
i+=sum;
//if(i<=MAX)
table[i] = '1';
}
}
void main()
{
long long i;
memset(table,'0',MAX);
for(i = 1;i<=MAX;i++)
{
if(table[i]=='0')
{
printf("%lld\n",i);
unself(i);
}
}
}
Pls help me!!!!!!!
Thanks in advence!!!
Amra korbo joy akhdin............................

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
hmm...
Well there is no reason why ur code should NOT get TLE. you are running a code with a complexity of O(1000000*1000000).
Your problem is in the unself part. You dont have to generate the whole sequence ... just cut off the number that can be generated by the current number i.e. 'n'.
Well there is no reason why ur code should NOT get TLE. you are running a code with a complexity of O(1000000*1000000).
Your problem is in the unself part. You dont have to generate the whole sequence ... just cut off the number that can be generated by the current number i.e. 'n'.
Where's the "Any" key?
selfnumbers
dear
i am new to this group
one of my student has derived a formulae to generate self numbers
that tooat the age of 16
it was approved by the cochin university
and he was congratulated by his highness the president of india
i am a mathematics teacher
i want to discuss this
and to introduce the boy to this group
kindly inform what to do
i am new to this group
one of my student has derived a formulae to generate self numbers
that tooat the age of 16
it was approved by the cochin university
and he was congratulated by his highness the president of india
i am a mathematics teacher
i want to discuss this
and to introduce the boy to this group
kindly inform what to do
self numbers
dears
i am new to this group
one of my student has derived a formulae for this
and that too at the age of 16
it was approved by the cochin university of acience and technology
and he was congratulated by his highness the president of india
he has proved googol is not a self number
and generated a formulae for this
he named the largest he found on his name
and that is 10*10^1000000
he had such immense intuition that he will deliver in seconds whether a number is a self number or not
i like to discuss this matter and like to introduce the boy to the group
i am a mathematics teacher who was working in trk higher secondary school in india
and now in mes indian school qatar
hope u all will reply
and being new i need to know how to discuss these in this group
thanking u
jagadeesh
i am new to this group
one of my student has derived a formulae for this
and that too at the age of 16
it was approved by the cochin university of acience and technology
and he was congratulated by his highness the president of india
he has proved googol is not a self number
and generated a formulae for this
he named the largest he found on his name
and that is 10*10^1000000
he had such immense intuition that he will deliver in seconds whether a number is a self number or not
i like to discuss this matter and like to introduce the boy to the group
i am a mathematics teacher who was working in trk higher secondary school in india
and now in mes indian school qatar
hope u all will reply
and being new i need to know how to discuss these in this group
thanking u
jagadeesh