Page 3 of 3
Posted: Wed May 17, 2006 11:21 am
by little joey
Sedefcho wrote:There is no mathematical formula. At least not till now
[...]
See this theorem. I think it can be used.
For even bases b the following can be proven:
If n ≥ b is a self number then n has the form n = (b-1) + a1(b^1+1) + a2(b^2+1) + ... with 0 ≤ ai < b.
Note that the reverse direction is not true.
[...]
Thanks for the hint!
Well, there is a mathematical formula. Let all the numbers generated by the formula that are not selfnumbers be called 'pseudo-selfnumbers'. If you list the pseudo-selfnumbers along with the coefficients a1, a2, ..., you will discover a regularity which will give an almost constant time algorithm to determine the rank of any selfnumber within the ordered set of all selfnumbers.
To the problemsetter:
Nice problem and a nice contest problemset!
Just one thing: I think it's better to avoid letting the input-format depend on the positions of line-breaks in the input-file. Even if you deliver a well formed input-file as problemsetter, you can never be sure what happens with it in the future; people may edit it, add or remove cases and then accidentally remove or add newlines. This happened on UVA on several occasions, leading to very hard to find bugs.
You could have avoided this, by adding a problem type indicator with every case, or writing it out explicitly:
Just my 2 cents worth of advice
thanks for the advice..
Posted: Wed May 17, 2006 2:09 pm
by sohel
little joey wrote:
To the problemsetter:
Nice problem and a nice contest problemset!
Thanks.
And, about the input format.. yes you are right. And i tried my best to make sure there was no error in the input file in terms of line break.
I will consider your advice, the next time i set a problem !!!
mamun wrote:
The gaps are not that periodic unless I misunderstood you.
Gap between first 5 consecutive self numbers is 2 and then 11 fro a while until we reach 108. Here we have another self number just after 2, ie. 110. Likewise we can see another variation in set {1006,1021,1032}. There are many more. Or did you mean periodic in this variation also?
you are right, it is not 100% periodic, but very close to 100.
If you observe closely, you will notice the periodicity.
Posted: Wed May 17, 2006 4:25 pm
by Sedefcho
little joey,
maybe there's some regularity ... if u say so...
i was just left with the impression that there's no regularity
after doing a quick check via google. and btw are u sure this
regularity continues above the number 10 000 000.
nice regularity if so ...
by the way ... this almost constant time that you are talking about
is it not some function of the count of the digits of the number?
if so then it is a logN algorithm. which is not bad of course.
Posted: Wed May 17, 2006 5:33 pm
by little joey
Good point. But the regularity looks so regular, that it has to be true
. I have the feeling that it is not too hard to prove, although that can be deceptive, of course.
Yes, by almost constant I meant dependent on the number of digits. But my implementation is rather clumsy and does the same amount of work for all numbers, even if they are much smaller than 10^7.
Posted: Mon May 29, 2006 1:10 pm
by temper_3243
for calculate function fun(a,b) we can do next:
precalculate array G[], where G = fun(0,i).
Than fun(a,b) = G - G[a-1], if a <= b.
If we see to this array we can do some conclusion about this numbers... For example G[27], G[35], G[99], G[143] we can evalute by next:
27 = 9 + 1 * 11 + 7;
than G[27] = 5 + 1 = 6;
35 = 9 + 2 * 11 + 4;
than G[35] = 5 + 2 = 7;
99 = 9 + 8 * 11 + 2;
than G[99] = 5 + 8 = 13;
143 = 9 + 3 * 11 + 1 * 101;
than G[143] = 5 + 3 + 1 * 10 = 18
I hope all is right ...
for all numbers from 1 to 10000001 I find out some rules that helps to evalute G without precalc in time near O(1).
But I cant to prove my algo by math
Why does the below code fail for numbers above 1002 . I mean i don't find the formula right. Can you please correct me.
Code: Select all
#include<cstdio>
using namespace std;
int ret(int n)
{
int a1,a2,a3,a4,a5,a6,a,t;
a=n-9;
a6=a/1000001;
t= a - a6*1000001;
a5= t/100001;
t= a - a6*1000001 - a5*100001;
a4= t/10001;
t= a - a6*1000001 - a5*100001 - a4*10001;
a3=t/1001;
t=a - a6*1000001 - a5*100001 - a4*10001 -a3*1001;
a2=t/101;
t=a - a6*1000001 - a5*100001 - a4*10001 -a3*1001 -a2*101;
a1=t/11;
printf("%d %d %d %d %d %d\n",a1,a2,a3,a4,a5,a6);
return 5 + a1 + 10*a2 + 100*a3 + 1000*a4 + 10000*a5 + a6*100000;
}
int main()
{
int n,k,b,z;
scanf(" %d",&n);
printf("%d\n",ret(n));
return 0;
}
test cases please
Posted: Tue May 30, 2006 10:30 pm
by temper_3243
Can someone give more test cases. Can someone tell me where my code is wrong . Please help me .
Code: Select all
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define mymax(a,b) ((a>b)?(a):(b))
int
ret (int n)
{
int a1, a2, a3, a4, a5, a6, a, t;
if(n<3)
return 1;
else if(n<5)
return 2;
else if(n<7)
return 3;
else if(n<9)
return 4;
else if(n<20)
return 5;
a = n - 9;
a6 = a / 1000001;
t = a - a6 * 1000001;
a5 = t / 100001;
t = a - a6 * 1000001 - a5 * 100001;
a4 = t / 10001;
t = a - a6 * 1000001 - a5 * 100001 - a4 * 10001;
a3 = t / 1001;
t = a - a6 * 1000001 - a5 * 100001 - a4 * 10001 - a3 * 1001;
a2 = t / 101;
t = a - a6 * 1000001 - a5 * 100001 - a4 * 10001 - a3 * 1001 - a2 * 101;
a1 = t / 11;
/* printf ("%d %d %d %d %d %d\n", a1, a2, a3, a4, a5, a6); */
return 5 + a1 + 10 * a2 + 98 * a3 + 978 * a4 + 9778 * a5 + a6 * 97778;
}
int
sod (int n)
{
int sum = 0;
while (n)
{
sum += n % 10;
n /= 10;
}
return sum;
}
int
isself (int k)
{
int i;
for (i = mymax (0, k - 72); i < k; i++)
{
if (i + sod (i) == k)
return i;
}
return -1;
}
int
main ()
{
int n, z, no, i, k, a, b;
char *y, *str, *t;
str = (char *) calloc (80, sizeof (char));
t = str;
fgets (str, 75, stdin);
while ((y = strtok (str, " ")) != NULL)
{
no = strtoul (y, NULL, 10);
str = NULL;
}
str = t;
for (i = 0; i < no; i++)
{
str = t;
fgets (str, 75, stdin);
printf ("Case %d: ", i + 1);
k = 0;
while ((y = strtok (str, " ")) != NULL)
{
if (k == 0)
a = strtoul (y, NULL, 10);
else
b = strtoul (y, NULL, 10);
k++;
str = NULL;
}
if (k == 1)
printf ("%d\n", isself (a));
else
{
if (isself (a)==-1)
printf ("%d\n", ret (b) - ret (a) + 1);
else
printf ("%d\n", ret (b) - ret (a));
}
}
return 0;
}
Re: test cases please
Posted: Wed May 31, 2006 5:23 am
by Martin Macko
temper_3243 wrote:Can someone give more test cases. Can someone tell me where my code is wrong . Please help me .
Your solution's not working for
The correct answer is
Code: Select all
Case 1: 0
Case 2: 1239987
Case 3: 1239992
Posted: Thu Jun 08, 2006 9:28 pm
by emotional blind
Nice Problem
Thanks Sohel
Now I lead the Function Overloading - ranklist
with 0.00.006
EDIT:Now : 0.00.004
So It is seen that time limit is not so harsh which was 1 sec in online contest!
Posted: Fri Jul 21, 2006 11:51 am
by StatujaLeha
Hi all! Please, give me some hint to avoid TLE. How I try to solve this problem now:
1. I found all numbers A for which there is number I such I + sod(I) == A. I remember it in bool IsSelfNumber[].
2. For numbers A < 5000001 i store in MyArr[A] number of numbers from punkt 1, which <= A.
3. I rewrite function fun(int a) so that it use IsSelfNumber[] and take at most 1000000 iteration to find answer.
Is there any other way to improve speed?
Posted: Fri Sep 08, 2006 7:17 pm
by Programmer
Hello.
Can someone who get AC tell me answer of this test.
1
1 10000000
Thanks.
Posted: Sat Sep 09, 2006 2:33 pm
by mamun
Programmer wrote:Hello.
Can someone who get AC tell me answer of this test.
1
1 10000000
Thanks.
Case 1: 977787
selfnumbers
Posted: Sun Oct 22, 2006 9:34 pm
by jagadeesh
dears
i am new to this group
i happened to see this discussion
one of my student has derived a formulae for this
and that too at the age of 16
it was approved by cochim university of sceince and technology
and and he was congratulated by his highness the president of india
he has proved googol is not a self number
and the largest number he found at that time was named on his name and that was 10 *10^1000000
he has an immense intuition and that he will deliver whether a no is a self number or not in seconds
and if not he will say from which number it was generated
i like to discuss this matter in this group and to introduce the boy to this group
i am a mathematics teacher who was working in trk higher secondary school india
and now in mes indian school qatar
hope u all will reply and this boy will be an asset to this group
we can give a hand
being new i like to know how to discuss this matter in the group and to send messages
kindly inform me in
jagadeeshsir@yahoo.com
thanking u
jagadeesh
WA NEED I/O
Posted: Thu Mar 22, 2007 8:09 pm
by SHAHADAT
PLEASE CAN ANY ONE GIVE ME SOME I/O.
I'm GETTING WA
Re: WA NEED I/O
Posted: Thu Mar 22, 2007 9:09 pm
by SHAHADAT
AC.BUT almost 3.8 seconds.
Terrible
