Problem se nalazi na
http://acm.uva.es/p/v1/100.html
+dodatak:Zamišljeno je da imam 1s da se dobije rješenje za pojedini interval
Zanima me smijem li ja ovdje primjenjivati grubu silu za rješavanje problema?
Recimo da za nijedan n nisam našao više od 300 koraka dok ne dođe do broja jedan(npr. za broj 999999 ima 258 koraka).Ako uzmem najgori mogući slučaj(interval [1,1000000]) tada,ako uzmem za svaki broj iz tog intervala 300 koraka,sve skupa imam 300 000 000 operacija. Ako je testno računalo cca 800 Mhz(cca 800 000 000 operacija u sekundi),to bi trebalo biti dovoljno,pretpostavljam. Jesu li dosadašnje pretpostavke točne?
Zamislio sam i malo drugačiji pristup,memorijski zahtjevniji. Nekako podsjeća na dinamičko programiranje. Recimo da za svaki n pamtim u poziciji DULJINA[n], broj koraka koji mu trebaju dok ne dođe do 1,a za neki broj m čiji se ciklus nadovezuje na broj n izračunam broj koraka baš pomoću podatka DULJINA[n].Kažem,memorijski je zahtjevniji(10 000 000 * 4 bajta,recimo),ali trebao bi biti brži.
Koji je način bolji,ispravniji, i postoji li još neka druga metoda za rješavanje?
I da,kako da učitavam podatke s tipkovnice(oblik je naveden na već navedenom linku) dok ih ima(while not FEOF(stdin) ne radi)?(pitanje nižeg prioriteta)