[ivank]

Время выполнения программы для даной задачи ограничено 1 секундой и обьем кода до 4кб. »

Обычно 64кб ограничение на размер исходника (по ACM'овским правилам).

Что такое контестер, что такое ACM и что такое контестер типра ACM? »

http://en.wikipedia.org/wiki/ACM_Int...amming_Contest

Так вот, если ограничение всё-таки 64 кб, то спокойно можно сделать таблицу. (длина десятичной записи n!) -> значение n. Длина для всех факториалов начиная с 10! точно различна (для значений меньше можно использовать честный подбор). Длина 2000! - 5737. Элементарная программа на питоне (или любом другом языке, в котором встроена поддержка больших чисел) легко позволяет построить такую таблицу за пару минут.

[DaRiYs]

Ну так у меня ограничение кода до 4 кб. Эт не АСМ а ему подобный

[ivank]

Если очень хочется извратиться и впихнуть всё в 4кб, то можно закодировать таблицу в виде сдвигов между соседними значениями. Т.к. мы умножаем максимум на 2000, то длина изменяется не более, чем на 4 знака каждый раз; но не менее, чем на один. Для хранения этой информации достаточно 2 бит. А для хранения всех сдвигов - 4000 бит, которые можно записать в виде строки (если использовать только печатные символы из нижней половины ascii, чтобы можно было вставить в исходный текст без изменений) всего в 4000/log2(64)=667 символов, ещё 3кб на код останется . И потом декодировать оттуда нужную информацию небольшим кусочком кода.

Всё решение будет типа такого:

Код:

unsigned char[] diff_table="blah-blah blah..."; //667 символов таблицы.

// получить i-й сдвиг из таблицы.
int getDiff(int i) {
    unsigned char c = diff_table[i/6] - 32;
    int diff = (c >> ((i%6)*2)) & 3; 
    return diff;
}
// ....
char fac_str[10000];
cin >> fac_str; // зачитываем факториал, _как строку_

int need_len = strlen(fac_str); // длина факториала, для которого надо найти n
int n = 0; // ответ будет здесь
if (need_len <= 8) {
    // n <= 10, тупо подбираем
    int facn = 1;
    int fac = atoi(fac_str);
    for (n = 1; facn < fac; ++n) {
        facn *= n;
    }
} else {
    int len = 8; // длина факториала 10
    // начинаем подбирать с 11
    for (n = 11; len < need_len; ++n) {
        len += getDiff(n);
    }
}

А можно, всё-таки, честно запрограммировать длинное умножение и не париться с извращениями. Ссылку в яндекс, где объясняется, как правильно умножать длинные числа, я уже бросал.

[Altair86]

Могу предложить еще вариант без длинной арифметики. Не знаю, будет ли он работать быстрее, поскольку там много вычислений с плавающей точкой... и влезет ли в нужный объем.
Правильно работать он будет, только если число в файле заведомо является факториалом.
Способ: приближенное значение натурального логарифма факториала числа n равно
ln(n!)=1/2(ln(2)+ln (Pi))+ln(n)+n*ln(n)-n
десятичный логарифм равен
Log(n!)=ln(n!)/ln(10)
Количество знаков в факториале будет равно Log(n!)+1, округленному снизу.
Считываем из файла факториал в виде символьной строки. Считаем количество знаков в этой строке. Дальше ищем на отрезке числовой оси (1;2000) нужное нам число n методом деления отрезка пополам. То есть, проверяем числа 1 и 2000 (считаем по формуле), если кол-ва цифр в их факториалах не подходят, берем число в середине отрезка (например 1000), считаем кол-во цифр в его факториале. Если опять не подходит, берем середину отрезка (1;1000) или (1000;2000)-- в зависимости от того, больше или меньше кол-во знаков в числе из файла, чем в 1000! Дальше снова, максимум за 10--12 шагов число n точно определяется
И одна тонкость: для чисел, меньших 7, лучше сохранить факториалы в файле с программой, и сначала проверять не является ли n одним из этих чисел. после чего делить отрезок не от 1 до 2000, а от 7 до 2000. (потому, что факториалы разных чисел, меньших 7, могут иметь одинаковое кол-во знаков)

[DaRiYs]

Мож хтонибудь всетаки напишет код на ассемблере для использования его в С++

[Admiral]

Можно на примере или прочесть где?! »

Пример для MSVS 6+

Код:

#include <Windows.h>
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
SYSTEMTIME st;
GetSystemTime(&st);//GetLocalTime()
cout << "\n" <<st.wSecond << " " <<st.wMilliseconds;
Sleep(1000);
GetSystemTime(&st);//GetLocalTime()
cout << "\n" <<st.wSecond << " " <<st.wMilliseconds;
return 0;
}

Для данного примера разницы между GetSystemTime() и GetLocalTime() нет. А вообще первая возвращает время по Гринвичу UTC, вторая по выбранному свойствах системы часовому поясу.

ivank, а как быть с iostream что б по стандарту? Или это » только в Linux, а micorosoft будет оставлять совместимость в своём компиляторе?
cout удобние printf
Или можно просто вывести значения st.wSecond и st.wMilliseconds через printf не усложняя код?
Со строчкой printf("%s %s",st.wSecond, st.wMilliseconds); компилится, но во время выполнения ошибка естественно

The instruction at "0x00000000" referenced memory at "0x00000000". The memory could not be "read".

Так как не совпадение типов. Чем собственно и удобен cout, что не брезгливый к этому. За это он не в стандарте?

[ivank]

Admiral,

ivank, а как бы по стандарту что в ситуации с iostream? Или это только в Linux, а micorosoft будет оставлять совместимость в своём компиляторе? »

Не понял вопроса Заголовочный файл iostream есть в стандарте и всегда будет и в gcc и в msvc. Нет в стандарте заголовочного файла iostream.h, который объявляет всё в глобальной области видимости (а не в std), но абсолютное большинство компиляторов его всё равно поддерживают, как раз для совместимости.

cout удобние printf »

Спорное утверждение Если попробовать вывести что-то с более-менее сложным форматом, то форматная строка printf намного удобнее (мне во всяком случае).

Со сторчкой printf("%s %s",st.wSecond, st.wMilliseconds); компилится но во время выполнения, естественно ошибка »

Все приличные компиляторы умеют выдавать warning на такой код, очень уж распространённая ошибка

DaRiYs, за вас никто ничего писать не будет. Вам предложили методы решения задачи (целых 3). Если вы чётко объясните, что вас в них не устраивает (или что непонятно), то можно будет продолжать диалог.

[Admiral]

ivank, вопрос навеян этим постом, я об этом в предыдущем посте указал », когда сказал про Linux.
Да я понимаю, что строка printf("%s %s",st.wSecond, st.wMilliseconds); ошибочна. Я к примеру показал сравнения с cout << "\n" <<st.wSecond << " " <<st.wMilliseconds; которой кроме себя самой не нужно приведения типов, что б не вызывать ошибку при выполнении.
Компилятор MS C++ 2008 Express прохлопал всё без Warnings, возможно по дефолтному уровню предупреждений не положено замечать эту строчку как потенциально опасной. Сам я использую в основном printf, но когда отлаживаю программу и ещё не знаю нужной функции приведения типов, использую cout, так как он их щёлкает как орешки и выводит мне нужное значение. Можно и Debug средствами среды узнавать значения переменных, но они не всегда доступны.

[ivank]

ivank, вопрос навеян этим постом, я об этом в предыдущем посте указал », когда сказал про Linux. »

Вероятно я там неясно выразился. <iostream.h> официально не существует, просто <iostream> - вполне есть в стандарте.

[Admiral]

ivank, не прошло и дня.
printf("time %02u:%02u:%02u:%03u\n", st.wHour, st.wMinute, st.wSecond, st.wMilliseconds);
и ни каких сout с #include <iostream> и using namespace std;
а лишь printf c #include <stdio.h>
нашёл здесь.