10433 - Automorphic Numbers

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

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Apr 15, 2004 8:21 am

From ranklist I suppose, that exist way to not hard-code 2k-digits automorhic number, but generating it in program. Can anyone help me and tell me how can I do this ? Unfortunatly I got Accepted using hard-coded number. I don't like such way (this is first program in which I made it :( - I always want to find way in which I can generate data in program ... ).
If anyone can help me - please send me a hint. I know that I can generate number in such way (but It got TLE):

1. get the number of N digits, for examle 5
2. generate number xN, using following algorithm:
3. try every digit 0..8 for x and calculate sqrt(xN); if sqrt(xN) has the same all digits at the end of xN this is good number and go to 2

If I correct think, this algorithm has time complexity O(NlogN) where N is number of digits.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Apr 17, 2004 8:00 am

One thing I can say to DM,

I have solved the problem by precalculation.
First generate all the numbers ending with 5 and then 6.
A great property of automorphic number is that,
antumorphic number of (n+1) digit ending with 5/6 contains automorphic number of n digits ending with 5/6.

To be clear,

5
25
625
x625
yx625
zyx625
So, you need not to check the other digits..
What you need is to add 1-9 and check whether the number is automorphic and if this is, break there.
means,
25-automorphic
125-no
225-no
325-no
425-no
525-no
625-automorphic break;
try with 1625
2625
similarly..

After precalcultion you need to store two array of character,
one for ending with 6, another ending with 5.
Then for each query just use strcmp, or strstr type functions in c or c++;
--
Hope it will be clear to all of you.,..
Good day :D
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Sat Apr 17, 2004 7:05 pm

yes, it's clear to me anapum :)
but when I use such way, I got TLE :(
Maybe I do something wrong ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Sun Apr 18, 2004 5:06 am

you need not calculate the whole array for checking automorphic number..
For example,
25
25
---625
save the result and extend it for
625
625
--
do not calculate 25*25 again, just extend it for the last 6.
--
hope i am clear.. and it will help you..

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Sun Apr 18, 2004 12:15 pm

Thanks yahoo, now I know what I'm doing wrong :-) Nobody is perfect, but it's very nice, that still exist persons, which have fresh ideas for me :D

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Sun Jul 11, 2004 8:47 am

I used both the method of hard-code and check them one by one.
But I got both WA. Can anybody tell me why? Is there trciky cases besides 0 and 1? :cry:

I wonder if "0000" or "001" is correct?

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Sun Jul 11, 2004 6:43 pm

dunno why
i got WA too...
Impossible is Nothing.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Wed Jul 14, 2004 3:02 pm

Finally, i got AC when I translate my program from c++ to pascal...
Does anyone got any idea why this occur?
Impossible is Nothing.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Thu Jul 15, 2004 5:05 pm

I don't face any problem with c++.
In c++ you can ac the program by having an array of 2500 dig and then by searching the array only.
Just a code of 5 lines I think:-)

BTW, would you plz mention the problem you faced with c++?
--
"Everything should be made simple, but not always simpler"

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Thu Jul 15, 2004 5:50 pm

anupam wrote:I don't face any problem with c++.
In c++ you can ac the program by having an array of 2500 dig and then by searching the array only.
Just a code of 5 lines I think:-)

BTW, would you plz mention the problem you faced with c++?
--
I got WA in c++.
Let me pm my code to u~
Impossible is Nothing.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Jul 17, 2004 6:33 pm

send me your pascal program also.
"Everything should be made simple, but not always simpler"

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Thu Oct 07, 2004 2:08 pm

I suffered the same problem and got many WAs.

After that i realized the 2000 digits long const char array may cause the problem.

Just use "\" to break the long line, i get AC.

ie.
char r5[MAX+10] = "0302695456948792438016548848805106486276062082716415\
91325236097905009383854054263247198939318022098236001625451776810291593965045\
06657809033052772198385286341879645511424748536307235457049044509125214234275\
I think it may be the compiler's fault.
Anyone who knows why the compiler makes the program WA please "Private Message" to me(i can get it from the e-mail).

hope it will help.

Good luck.

[RiS]
New poster
Posts: 2
Joined: Wed Apr 14, 2004 4:26 pm

Post by [RiS] » Wed Oct 13, 2004 11:52 pm

WTF!

I had the same error.

I broke the strings with "\" and I get AC.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sat Mar 12, 2005 6:16 pm

I just wanted to clarify, if the number given is zero or one, then the judge considers it automorphic only if it has no leading zeros (in particular 0 and 01 are not an automorphic numbers). My program considers 1 to be an automorphic number, but I don't know if the judge has such a case.
I'm always willing to help, if you do the same.

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » Fri May 18, 2007 6:35 pm

yahoo wrote:you need not calculate the whole array for checking automorphic number..
For example,
25
25
---625
save the result and extend it for
625
625
--
do not calculate 25*25 again, just extend it for the last 6.
--
hope i am clear.. and it will help you..
This is helpful but it's not enough to get AC.
Here is the reason:
When we extend 25 to x25, we still have to multiply 25 by x!
Let y equal to 25. Then multiplying x25 * x25 is equal to ...
(100x + y) * (100x + y) = 10000x^2 + 200yx + y^2
y^2 is taken cared of and 10000x^2 is easy to compute. However, see the middle term 200yx. Every single digit of y still has to multiply with x and 2!! As y is can be as large as 2000 digits, more has to be done to reduce the time.

Does anyone have any more hints??

Thanks

Post Reply

Return to “Volume 104 (10400-10499)”