10433 - Automorphic Numbers

[Dominik Michniewski]

Can anyone tell me, how can I generate this numbers instead of computing square and check last digits? This method is too slow ( I got TLE). I know that only numbers ending with 5 and 6 are possible to be automorphic ...

Maybe is any fast matemathical method to solve this problem ? Could anyone tell me something about it ?

Thanks in advance
Dominik Michniewski

[Ghost77 dimen]

The reason causing the TLE ocurrance is the test data contain some

instances which are longer than 2000 digits.

By the description of the author, there will not be any Automorphic

Number contain more than 2000 digit.

So you can set an examination to delete the illegal data before the

array multiplication.

But it only reduce the time downto seven seconds.

Besides, my code is still wrong.

And what is the reply for the sample 01?

01==1 or 01!=1

[Dominik Michniewski]

I think, that's right. That can be TLE. But why not RTE ?????

It's must be some algorithtm to check it, because people has time less than 1 second (

I check on MathWorld pages, but there isn't any hint ((

Dominik

[gawry]

I think, that's right. That can be TLE. But why not RTE ?????

It's must be some algorithtm to check it, because people has time less than 1 second (

I check on MathWorld pages, but there isn't any hint ((

Dominik

There are only two numbers with the same length and their sum is 10^(length+1), so you can preprocess it.

[Rossi]

Try this link..
http://www.wschnei.de/digit-related-num ... mbers.html
There are some properties of it & also a Huge (10,000 digits) Automorphic Number. Think alittle how to preprocess it from the bigger one...

Rossi

[Dominik Michniewski]

Thanks all for help )
I try to solve this problem today )

Dominik

[razibcse]

Hi everybody,

I got this problem AC...
I first generated both the 2000-digit automorphic numbers in a seperate program because it took a lot of time...then I checked
the digits from the last with the digits of input number,because an automorphic number contains all the smaller automorphic numbers...
But I know this is not a good process...I want to find some algorithm that determines the type of the input number within the program...
If anyone of you know such process, let me know...

Razib

[Syed Mubashshir Husain]

Hi
Few days ago I got AC 10106. So, I do string multiplication for 10433.
But got TLE.

But Whyyyyyyyyyyyyyyyyyyy!

---
SMH

[laboni]

Can anyone help me with some critical input output?
I donno why i am getting WA.

What does "leading zeros must be considered as significant. " mean?

Bye

[deddy one]

I'm having a problem with that statement too,
could anyone tell me the right output for this
input :

Code: Select all

0000001
001
000025
025
0005
0000000076
111
0111
00111

thx.

[anupam]

as i know, a clarification was given during the contest.
please tell us what it was...
Thanks..
--
Anupam

[Red Scorpion]

"leading zero is significant" mean you must consider the leading zero as numbers.

Dedy the output for all your test case is "Not an Automorphic number.".

[anupam]

thanks but is there any faster way to generate all the numbers runtime than pregeneration?

plz give a better alg.

[Deno]

I have no ideal why did I get WA?

Code: Select all

#include <iostream> 
#include <string> 
#include <algorithm> 

int main(int, char**) 
{ 
   using namespace std; 

   const string end5("077347828...omit...8212890625"), 
             end6("9226521714...omit...1787109376"); 
   string str; 
   while(cin>>str) 
      if ( str == "1" || equal(str.rbegin(), str.rend(), end5.rbegin()) || equal(str.rbegin(), str.rend(), end6.rbegin()) ) 
         cout<<"Automorphic number of "<<static_cast<unsigned int>(str.size())<<"-digit."<<endl; 
      else 
         cout<<"Not an Automorphic number."<<endl; 
} 

First, I save two 1-Automorphic number (end with 5 and end with 6) by string class
Then compare the input data with the end of these two 1-Automorphic numbers
If the input data is 1 or it appear in any ending of two 1-Automorphic numbers, then it is an Automorphic number; otherwise it is not

Where did I get wrong?

The two 1-Automorphic numbers I got are:

end with 5:

077347828544986864086656739926957808216228357260302695456948
792438016548848805106486276062082716415913252360979050093838
540542632471989393180220982360016254517768102915939650450665
780903305277219838528634187964551142474853630723545704904450
912521423427595549184397398445871252869481982692702925526483
490320652685127220296131869994777653548129151985764042296818
309177344527772320073760382588317272927956365741901444523595
431910306357249617898820317578776106213770808096781137493191
176656303149020578435250957288066846412106925280227506129851
161620638400677897940244902387511125868953454951488820067866
770234100283954928297028644727362521753544319791185506815726
485880485267387168480400218852947302222334454122132846484415
359379366313360445894032872347840194735756036134621200867537
334691331433871735088021260028575298538664393102232655345477
684502995702556165814337023650207474485681478787290209241258
290530124912466886835158767749989176867871572813494087927689
452979709777230540335661882819870221063055796723980661119019
774464242102513674870111713127812540013369008603488908436402
387576593682197962618191783352049270419932487523782586714827
890534489744014261231703569954841949944461060814620725403655
999827158835603504932779554074196184928095209375302685239093
756283914857161236735197060922424239877700757495578727155976
741345899753769551586271888794151630756966881635215504889827
170437850802843408441264412682184851415772991603449701789233
579668499144738956600193254582767800061832985442623282725755
611073316069701586498422229125548572987933714786632317240551
575610235254399499934560808380119074153006005605574481870969
278509977591805007541642852770816201135024680605816327617167
676526093752805684421448619396049983447280672190667041724009
423446619781242669078753594461669850806463613716638404902921
934188190958165952447786184614091287829843843170324817342888
657273766314651910498802944796081467376050395719689371467180
137561905546299681476426390395300731910816980293850989006216
650958086381100055742342323089610900410661997739225625991821
2890625

and end with 6:

922652171455013135913343260073042191783771642739697304543051
207561983451151194893513723937917283584086747639020949906161
459457367528010606819779017639983745482231897084060349549334
219096694722780161471365812035448857525146369276454295095549
087478576572404450815602601554128747130518017307297074473516
509679347314872779703868130005222346451870848014235957703181
690822655472227679926239617411682727072043634258098555476404
568089693642750382101179682421223893786229191903218862506808
823343696850979421564749042711933153587893074719772493870148
838379361599322102059755097612488874131046545048511179932133
229765899716045071702971355272637478246455680208814493184273
514119514732612831519599781147052697777665545877867153515584
640620633686639554105967127652159805264243963865378799132462
665308668566128264911978739971424701461335606897767344654522
315497004297443834185662976349792525514318521212709790758741
709469875087533113164841232250010823132128427186505912072310
547020290222769459664338117180129778936944203276019338880980
225535757897486325129888286872187459986630991396511091563597
612423406317802037381808216647950729580067512476217413285172
109465510255985738768296430045158050055538939185379274596344
000172841164396495067220445925803815071904790624697314760906
243716085142838763264802939077575760122299242504421272844023
258654100246230448413728111205848369243033118364784495110172
829562149197156591558735587317815148584227008396550298210766
420331500855261043399806745417232199938167014557376717274244
388926683930298413501577770874451427012066285213367682759448
424389764745600500065439191619880925846993994394425518129030
721490022408194992458357147229183798864975319394183672382832
323473906247194315578551380603950016552719327809332958275990
576553380218757330921246405538330149193536386283361595097078
065811809041834047552213815385908712170156156829675182657111
342726233685348089501197055203918532623949604280310628532819
862438094453700318523573609604699268089183019706149010993783
349041913618899944257657676910389099589338002260774374008178
7109376

Thank you!

[[RiS]]

Hi everybody,

I got this problem AC...
I first generated both the 2000-digit automorphic numbers in a seperate program because it took a lot of time...then I checked
the digits from the last with the digits of input number,because an automorphic number contains all the smaller automorphic numbers...
But I know this is not a good process...I want to find some algorithm that determines the type of the input number within the program...
If anyone of you know such process, let me know...

Razib

I've generated the numbers too...
but I get WA I'm *sure* that the 2 numbers are Ok...

Any idea?