0

Решаю задачу на E-Olymp.

Мой код:

int _tmain(int argc, _TCHAR* argv[])
{
    double n, kol = 1, sum = 0;

    cin >> n;

    for (int i = 0; i < (n*n); i++)
    {
        sum += kol;
        kol *= 2;
    }
    printf("%.0f\n", sum);
    system("pause");
    return 0;
}

Сайт проверяет на входное значение 10. double, как я понял, для этого не помощник ибо ограничен. Подскажите пожалуйста, как можно реализовать?

12
  • 1
    В столбик в школе перемножать числа Вас не учили? Вот прямо так алгоритм перемножения двух чисел и расписываете. А результат записываете ввиде обычной строки.
    – Max ZS
    20 мар 2016 в 20:58
  • 1
    Сменить язык на джаву для этой задачи...
    – Qwertiy
    20 мар 2016 в 21:13
  • 1
    e-maxx.ru/algo/big_integer
    – Qwertiy
    20 мар 2016 в 21:13
  • @Qwertiy А что Java даст?
    – Max ZS
    20 мар 2016 в 21:14
  • @MaxZS, там есть BigInteger встроенный.
    – Qwertiy
    20 мар 2016 в 21:15

1 ответ 1

2

Из принципа пришлось решить задачу, прошла, даже - просвистела на второе место :) очень быстро.

Мы точно можем оценить максимальный размер числа, так что знаем, какой массив данных нам понадобится. Я пошел по пути N*N удвоений, с последующим вычитанием 1. Нам нужны только две операции - удвоение и вычитание 1. Берем массив в 350 (с запасом) unsigned long, и N*N раз удваиваем (суммируем соответствующие элементы, выполняем, если надо, перенос). Чтоб быстрей потом преобразовывать в десятичное - в каждом элементе массива значения ограничены одним миллиардом. Отслеживаю размер числа - чтоб не суммировать лишнее...

Я, конечно, могу привести тут код, но не уверен, насколько это хорошо в смысле педагогическом :) Чуть-чуть покажу все же.

class bigNum
{
public:
    bigNum() { a[0] = 1; }
    void mul2();
    void dec() { a[0]--; }
    void out();

private:
    static const int size = 350;
    static const int lim  = 1000000000;
    unsigned long a[size] = { 0 };
    int last = 1;
};

void bigNum::mul2()
{
    unsigned long carry = 0;
    for(int i = 0; i < last; ++i)
    {
        a[i] *= 2;
        a[i] += carry;
        if (a[i] >= lim)
        {
            carry = a[i]/lim;
            a[i] %= lim;
        }
        else carry = 0;
    }
    if (carry)
    {
        a[last++] = carry;
    }
};

P.S. Для подъема скорости можно множить, скажем, на 16 или там 64, соответствующим образом меняя размеры...

5
  • dec() не будет работать, если a[0] == 0
    – int3
    24 мар 2016 в 17:43
  • @int3 По условию задачи - 2^N-1 - это невозможно, не правда ли? :)
    – Harry
    24 мар 2016 в 17:46
  • класс всё-таки называется bigNum, а не solver ;) Для задачи не принципиально, да
    – int3
    24 мар 2016 в 17:50
  • Условный оператор в цикле - лишний, только замедляет. Но, вообще говоря, тут надо тогда уж использовать быстрое возведение в степень... 24 ноя 2016 в 5:42
  • В быстром возведении в степень есть произведение длинных целых. Простейший алгоритм для которого квадратичный. Получится решение за квадрат. Так оно и сейчас за квадрат, только проще, значит константа меньше. 14 ноя 2021 в 18:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.