• Как принять число любой длины?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам не только принимать числа любой длины в конструкторе, вам их хранить и обрабатывать придется. Чтобы работать с данными любой длины придумали массивы. Например, передавайте строку или std::vector.
    Ответ написан
    Комментировать
  • В чем может быть проблема не считывания с файла?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Смотрите внимательно, что программа выводит. Где там пробел выводится-то?
    Ответ написан
    Комментировать
  • Как упростить код?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ну вот ваше последнее описание и есть решение - храните 2 стека. Вы же храните 1 стек и лишь в определенном случае заводите второй стек tmp.
    Ответ написан
    Комментировать
  • Как бы упростить непростое сравнение строк?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Фактически у вас тут запросы, "найти строки где много нулей на этих произвольных позициях". Никакого предподсчета я тут не вижу. Можно здорово ускорить, если хранить от строк только битовые последовательности (где '0' заменяется на единичный бит). Далее каждую строку надо про AND-ить побитово с новой и подсчитать количество единичных бит. Это теооетически раз в 64-100 ускорит вычисления, если 64-битный целый тип использовать. Или еще несколько раз сверху, если использовать векторизацию. Но как это в php сделать, я не знаю.

    Даже без 5% ошибок оно не оптимизируется предподсчетами. Тупо найти строки, в которых '0' вот на этих позициях - особо не наоптимизируешь.
    Ответ написан
  • Как извлечь элементы многобайтового массива как единое число?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Лучше так делать не надо. Это UB - нарушение всяких strict aliasing, выравниваия и вообще от порядка байт в машине зависит. Лучше руками собрать ULL по частям, вроде
    for (int i = 0; i < 8; ++i) result |= byte_array[i+1] << (8ULL*i);
    или
    for (int i = 0; i < 8; ++i) result |= byte_array[i+1] << (8ULL*(7-i));


    На худой конец, если очень узкое место, надо делать memcpy из массива в &result.
    Ответ написан
    Комментировать
  • Почему явная специализация невозможна?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема вызвана использованием шаблона rewrite из шаблона search.

    Если вы перенесете специализацию шаблона rewrite вверх, до специализации search, то все скомпилируется. Или надо где-то выше первого использования шаблона rewrite задекларировать специализацию (что ваш закомментированный код и делает).

    Вызвана эта ошибка стандартом.
    Надо, чтобы специализация шаблона была задекларирована до любого использования:
    Specialization must be declared before the first use that would cause implicit instantiation, in every translation unit where such use occurs:
    Ответ написан
    1 комментарий
  • Уменьшается ли используемая память программы?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Не гарантированно, но в некоторых случаев компилятор действительно сможет переиспользовать место на стеке под переменную a для какой-то новой локальной переменной, когда a выйдет из зоны видимости. Но чаще это место просто будет пустым до конца функции и никакой экономии памяти вы не получите.

    Но вообще, делать так для экономии памяти никогда, категорически не рекомендуется. Код становится менее читаем а экономите вы на спичках. Это локальные переменные - они на стеке. Их много можно выделить только рекурсией или большими массивами (ну не объявите вы в коде миллион локальных переменных). В обоих случаях, если стека не хватает - надо или избавлятся от рекурсии/больших массивов изменением логики, или выносить их в кучу.

    Использование фигурных скобок для ограничения зоны видимости переменной действительно используется на практике, когда вам надо ограничить время жизни переменной и добиться вызова деструктора в определенное время. Так делают, например, когда захватывают мютекс в многопоточных программах - специальный класс-обертка в конструкторе его хватает, в деструкторе освобождает. И иногда не надо держать мютекс во всей функции, а только в определенном месте. Допустим, дальше идут долгие вычисления, не требующие мютекса. Тут логично мютекс освободить. Но это должно встречаться редко. Если вам в функции надо несколько раз такое проворачивать, то надо ее отрефакторить и разбить на части.
    Ответ написан
    Комментировать
  • В чём отличия языка Си и С++? Зачем нужен Си?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    По учебнику, фундаментальных отличий три: классы, шаблоны и исключения. По факту там еще целый ворох мелких различий и это два вообще разных языка, хоть и слегка похожих.

    C сейчас используется в основном там, где легаси (куча старого кода в проекте уже на C), или где очень жесткие требования к легкости окружения исполнения языка (микроконтроллеры всякие).
    Ответ написан
    2 комментария
  • Корректно ли в C++ называть стек статической памятью?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Стек стоит рассматривать как отдельную категорию. И статической памятью его называть точно не стоит.
    Хотя бы потому, что для работы с ним есть специальные команды процессора.
    Плюс, он хоть и выделяется программе при загрузке, в отличии от статических данных, обращаться к данным в нем можно не всегда - а только ниже по стеку вызовов.
    Ответ написан
    Комментировать
  • Как начертить правильный n-угольник с центром в точке (x, y) на поверхности шара?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Удобно ввести новую систему координат и потом откладывать ее базисные векторы нужное количество раз.
    Эта система будет иметь центр на радиусе сферы к центру оружности и лежать на "хорде" - плоскости в которой лежит многоугольник. В ней ваш многоугольник будет просто на плоскости.

    Из простейшей геметрии вы знаете, что этот центр координат будет на расстоянии sqrt(R^2-r^2) от центра сферы - так радиус окружности на сфере будет r.

    Первый базисный вектор будет вдоль радиуса из центра сферы к центру многоугольника и координата там будет всегда 0.
    Теперь вам надо найти еще какой-то вектор в плоскости многоугольника, а третий вектор потом найдете через векторное произведение. Хорошо бы этот второй вектор взять на север, тогда ясно куда класть первую точку по условию. Если только центр окружности не лежит строго на свере, то можно взять и спроецировать на плоскость вертикальный вектор (0, 0, 1) и все (а в противном случае проецируйте, допустим (1, 0, 0). А дальше останется только взять формулы для многоугольника на плоскости x = cos(2*pi/n*k)*r y = sin(2*pi/n*k)*r, ну и не забыть перевести все в обычную систему координат.

    Итак, пусть xo,yo,zo - точка на сфере, где лежит центр. xo и yo не нули одновременно. Еще даны R, r и n.

    Центр новых координат:
    L = sqrt(R^2 - r^2)
    x1 = xo/R*L
    y1 = yo/R*L
    z1 = zo/R*L

    Первый базисный вектор:
    e1 = (x0, y0, z0) / R
    Второй базисный вектор (нормализованный (0,0,1) - (0,0,1)*e1):
    e2 = (-x0*z0/R/sqrt(R^2- z0^2), -y0*z0/R/sqrt(R^2- z0^2), sqrt(R^2-z0^2)/R)

    третий базисный ветор, найдите сами через векторное произведение.

    А дальше координаты k-ой точки:
    p = (x1,y1,z1) +e2*cos(2*pi/n*k)*r+e3*sin(2*pi/n*k)
    Ответ написан
    Комментировать
  • Скажите как можно исправить тайм лимит в коде?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Сумму на отрезке надо делать хитро: в каждой вершине поддерживайте счетчик, сумму значений всех вершин в поддереве, а так же минимальное и максимальное значение в поддереве.

    Рекурсивно спускайтесь, если текущее поддерево целиком лежит в запросе - возвращайте известную сумму.
    Иначе запускайтесь слева или справа только если отрезок там пересекается. Или можно просто возвращать 0 вместо этих проверок, если все вершины в поддереве не попадают в отрезок (меньше левой границы запроса или больше правой). Такой подход найдет сумму за O(log n) а не за O(n).
    Ответ написан
  • Как создать массив из типов данных в си?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если массив фиксирован, то можно попробовать через variadic macros это сделать. Но это такой ужас получится. Вам же кроме размеров типов что-то еще делать надо с разными типами. Проще завести enum типов данных, массив из этого, и через switch считать размеры для каждого значения enum.

    Edit: был не прав: variadic macro тут не поможет.
    Ответ написан
  • Более общее свойства дерева поиска?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Что за last_key? Почему дерево считается неправильным, если самая левая вершина равна numeric_limits<int>::min()

    Эта задача, в отличии от предыдущих двух ваших вопросов - простая. Тут не надо писать балансированное дерево поиска, а надо тупо проверить, что заданное дерево хорошее.

    Отличие от прошлой задачи, упомянутой в вопросе - только в том, что теперь ограничения в каждом поддереве не L < key < R, а L <= key < R. Т.е. отличие от кода в конце вопроса, по идее, должно состоять только в одном знаке <= вместо <

    Есть, правда, дополнительная проблема, что числа могут быть очень большие и, например, надо было бы в самом начале передавать numeric_limits<int>::max()+1 в качестве правой границы. Но тут можно решить эту проблему просто заменив тип параметров max_key, min_key на long long. Или изменить их смысл на "ключи в этом поддереве могут быть с L по R включительно". Тогда при переходе к левому сыну надо бы передавать tree[i].key-1 в качестве max_key. Но тогда надо аккуратно и не переполниться при numeric_limits<int>::min(). Но тут тогда нужна дополнительная проверка - любая вершина со значением numeric_limits<int>::min() не должна иметь левых детей.
    Ответ написан
    Комментировать
  • Что быстрее: создание вектора push_back или сначала объявление сколько в нем переменных, а потом заполнение?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Сначала объявление будет быстрее. Тут всего одно выделение памяти, а при push_back их будет несколько (но не n, потому что vector умный и выделяет памяти с запасом).

    Но push_back не на порядок медленнее. В худшем случае в пару раз. И то и другое будет работать за O(n). Если у вас программа еще хоть что-то делает, кроме запихивания чисел в массив, то вы разницу особо и не заметите.

    Если только профайлер не показывает что вот это вот самое медленное место в программе, то заморачиваться не стоит.
    Ответ написан
    3 комментария
  • Можно ли передать тип данных как параметр функции?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    В C - нет. В C++ можно воспользоватся шаблонами. Но если вопрос действительно про C, то надо передавать в функцию какой-нибуть enum где все возможные типы перечисленны. Или, как в scanf, передавать идентификатор типа в строке.
    Ответ написан
    6 комментариев
  • Множество с запросами?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ваше решение медленно считает сумму на отрезке. За O(n) - вы проходитесь по всему множеству. А все ваше рение будет O(n^2). Когда как это надо делать за O(log n) максимум. Ну посмотрите же на ограничения - n <= 10^5. Обычно n^2 работает ну до 10^4 максимум с огромным скрипом и натяжками.

    К сожалению, стандартными set'ами вы сумму на отрезке быстро не подсчитаете. Придется реализовывать сбалансированное бинарное дерево поиска, где в каждой вершине надо дополнительно хранить сумму всех значений в поддереве. Вот реализация дерева, но там сумма на отрезке не реализована. Однако, в статье расказанно, как это делать. Ищите на странице "на отрезке".

    Если бы числа в задаче был поменьше, то можно было бы использовать дерево отрезков. Это сильно проще реализуется. Но тут бы это потребовало массивы на 2*10^9 элементов.

    Edit: вообще, судя по нескольким вопросам от вас, у вас там задачи именно на реализацию бинарных деревьев поиска с дополнительными данными в вершинах. Вот если у вас следующая задача опять не пройдет по времени, то сначала убедитесь, что вы используете собственноручно написанное дерево поиска.
    Ответ написан
  • Как лучше\проще реализовать работу с серийными номерами\лицензиями чтобы не особо пиратили?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Единственный способ запретить нелецинзионное копирование вашей программы - это вынести что-то важное в серверную часть. Там логин/пароль пользователя, плюс проверки на отсутствие параллельных сессий.

    Все остальное ломается.

    Следующий плохой вариант: делать слепок системной информации, при активации лицензии подписывать его на сервере приватным ключем. Программа открытым ключем проверяет, что файл лицензии корректен (расшифровывает и смотрит, что системная информация совпадает).
    Ответ написан
    Комментировать
  • Почему код не проходит по тайм лимиту?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    С такими ограничениями надо менять алгоритм. У вас наивная реализация за O(nq). А надо реализовывать rope за O(q log n).

    Какими-то стандартными контейнерами это не сделать вообще никак.

    Советую реализовывать декартово дерево по неявному ключу. Это самая простая реализация будет. Ну, а дальше вам надо будет это дерево разрезать на три части двумя Split, две крайние объеденить, разрезать это в новом месте и слить уже 3 части с вырезанным куском в середине.
    Ответ написан
  • Как работает данный алгоритм проверки числа на простоту и какой у него Big O??

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это вроде как решето Эратосфена (только с багами).

    Этот цикл по идее помечает составными все числа, делящиеся на i (которое к этому моменту вроде как простое). Таким образом все составные числа должны быть помечены в массиве a.
    Тут есть оптимизация: помечаются только те числа, для которых i - делитель не больше корня. Иначе бы цикл был не от i*i а от i. Эту оптимизацию можно делать, потому что у каждого числа обязательно есть простой делитель не больше корня, а значит и такой цикл пометит все составные числа.

    Сложность тут O(n log(log n)) - Доказательство смотрите в википедии.
    Ответ написан
    Комментировать
  • Как классифицировать числовой ряд?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Это называется кластеризация. Вам надо разбить данные на 3 кластера. Метод ближайших соседей, упомянутый выше, подходит.

    Все-таки все эти методы кластеризации разработаны для более общего случая. А у вас тут данные одномерные и численные уже - так что все совсем просто.

    Во-первых, данные надо отсортировать, если уже не. А дальше у вас тут 2 переменные - (i,j) - первый и последний элемент в средней группе.i>0,j<n-1.

    Можно эти индексы тупо перебрать двумя вложенными циклами. А дальше надо считать какую-то целевую функцию - насколько хорошо кластеры выбраны и брать лучшее значение. Надо, чтобы внутри различие было поменьше, а между кластерами - побольше. Можно брать максимум разности в каждом кластере и делить на разницу между двума кластерами. Вот минимизируйте эту функцию.

    Но вообще можно, наверно, просто взять 2 максимальных промежутка между соседними числами и по ним разделить. В примере выше этот метод отлично разбивает на 3 группы: 1-103, 999-1001, 9000-9500

    Если разность между маленькими числами важнее разности между большими, то возьмите сначала логарифм от всех чисел и уже это разбивайте на группы.
    Ответ написан
    7 комментариев