Благодаря!

Много полезен съвет, но в този случай не мога да го използвам защото при намиране на първи цифри 1234543, n = 176109, което е число от 53014 цифри.Това число не се побира в който и да е тип за С, затова използвам масив.

Може би тази задача има решение, може би е "мотичка", която авторите са поставили за забавление, но най-вероятно нямам достатъчно изчислителна мощ на компютъра и търпение:(  Последния тест, който направих бе до n = 1005000, но решение не бе намерено. Оставих компютъра да работи цяла нощ, за да превърти всички n!

Програмата може да се оптимизира, като 123454321 се постави в масив и се сравняват последните 9 елемента. Ако някой е получил решението моля, да го сподели!

Поздрави!

Ето и кратко доказателство, че 70,279,608 наистина е решение, т.е. 2^70279608 започва с цифрите 123454321.

Първо изчисляваме 70279608 log 2 = 21,156,270.091506298118993045735591.... Тогава 10^0.091506298118993045735591 = 1.2345432183309575226143399297209... т.е. 2^70279608 наистина започва с цифрите 123454321.

Този метод се използва за да се изчислят началните цифри на много големи числа, които не могат да се поберат в компютър. Например 123^456789 започва с цифрите 4633928101.... Неудобство на метода е това, че следващите цифри са неточни заради натрупване на грешки от закръгляването.

Иначе не се сещам за по-добър алгоритъм. Обаче предложената програма може да се направи малко по-бърза.

Използвам темата, за да кажа две думи за подобна, но по-лесна задача - за това как се изчислява на колко нули завършва n! (имаше някъде в упражненията такава задача). Броя на нулите е равен на степента на 5 в каноничното разлагане на n! и не е необходимо да изчисляваме колко е n! (това се учи в 5-ти клас, доколкото си спомням). Код на C#

            int n = int.Parse(Console.ReadLine()),
                numZeroes = 0;

            for (int i = 5; i <= n; i *= 5)
                numZeroes += n / i;

            Console.WriteLine(numZeroes);

Бързо и лесно, особено за големи стойности на n. Не съм го тествал в Джаджа, но съм сигурен, че работи.

MartinBG, я пробвай това

#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <time.h>

#pragma GCC optimize("O3")

#define GOAL  123454321
#define TOINT 100000000.0

int main(void)
{
	int i;
	double d;
	register const double LOG2 = 0.30102999566398119521373889472449;

	clock_t begin = clock();
    for(i = 0; i <= INT_MAX; i++)
	{
		d = i * LOG2;
		if (GOAL == (int)(pow(10.0, d - (int)d) * TOINT))
			break;
	}
	clock_t end = clock();
	
	printf("%d\n", i);
	printf("Time: %.2f sec\n", (double)(end - begin) / CLOCKS_PER_SEC);

    return 0;
}

и сподели колко ти изкарва. 

Алгоритъмът, който ползваш, изглежда да е най-ефективният познат (така пише в нета :)

Като микро оптимизации съм махнал modf() и константата съм я дефинирал като register. Това подсказва на компилатора да държи стойността в някой от регистрите, с което обаче може и да не се съобрази. Викането на функция в цикъл винаги бави (особено, ако ще се вика 70 милиона пъти), така че е хубаво да се елиминира до колкото може. O3 флага сваля към 0.01% от времето (поне при мен).

На i5 3.2GHz най-бързо се сметна за 5.39s

Поздрави!

@vlad.dinev

Благодаря за включването в темата! :)

Замяната на modf() с "d - (int)d" е добра идея! Не знам как съм пропуснал да го направя, при условие, че знам за този метод и съм го използвал многократно. 

Не знаех за register директивата при декларирането на променливи - пак научих нещо ново!  :)

Въпреки оптимизациите, обаче, времето за изпълнение на двете програми на моя лаптоп е горе-долу еднакво  - около 15 секунди.

Това най-вероятно е заради спецификите на лаптопа и Power management-a му. На "нормална" система твоята версия на програмата би следвало да се представи по-добре от моята.

Поздрави!

@MartinBG моля, пак заповядай. До сега не се бях сблъсквал с тази задача, научих нещо ново.

При мен разликата между твоята и моята версия е към 1.5s

Ще я пробвам после и на по-слаба машина и ще споделя, че ми стана интересно.

Поздрави!