Задать вопрос
  • Почему мой код считается медленным?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ваш алгоритм работает за O(n^2). Вы для каждого числа в массиве считатете, сколько раз оно туда входит проходя по массиву через nums.count(i). Оптимальное же решение работает O(n). Надо в хеш-таблице подсчитать, сколько раз каждое число встречается, потом через алгоритм QuickSelect выбрать k-ый c конца элемент.

    Ну, или можно за O(n log n) отсортировать массив и потом за один проход подсчитать сколько раз каждое число встречается. Дальше можно второй раз отсортировать по количеству вхождений и выдать k-ый элемент. Это решение тоже пройдет.
    Ответ написан
  • Стоит ли очищать оперативную память от массивов структур в Си?

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

    Надо вызывать free только для тех блоков памяти, который вы сами получили через malloc.
    Ответ написан
    Комментировать
  • Есть ли у этого название?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Зависит от того, что вы хотите получить, деля 15 на 2. Ясно что тут пять троек, а вот сколько там двоек?

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В тексте задания уже есть ответ на ваш вопрос:
    To better utilize memory, the list should include an array T=8 of structures representing a block


    Для экономии памяти. Такие гибридные структуры обладают характеристиками средними между списком и массивом. В список можно быстро вставлять и удалять из него элементы. В массивах можно быстро искать k-ый элемент и он занимает меньше памяти (не нужны указатели).

    Ваша структура позволяет добавлять и удалять элементы быстрее чем в массиве, но при этом занимает меньше памяти чем просто список, хоть и добавление и удаление элементов там медленнее, чем в списке.
    Ответ написан
    Комментировать
  • Как разрешить использование только конкретного наследуемого от интерфейса, не финального класса?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Практически никак. Суть полиморфизма в том, что экземпляры наследников можно вставлять вместо экземпляра предка везде и все будет работать. Поэтому вы средствами языка никак не запретите передавать C вместо B (речь об указателях, естественно). Если хочется, то можно сделать виртуальную функцию, которая возвращала бы какое-то enum, для идентификации классов A,B,C (и других наследников) и уже в функции проверять, что там не передали по ошибке экземпляр C. Но логичнее было бы выделить каие-то свойства у классов (например, количество пуль в вашем примере с MultiGun) их задать в виртуальных функциях у всех классов и дальше в функции проверять, что переданный экземпляр обладает нужными свойствами. Жестко привязываться, что можно B, но нельзя C - это плохой подход. Почему нельзя? А если потом появится D,E,F - можно ли их передавать? А если они братья B?
    Ответ написан
    Комментировать
  • Имеется ли в C++ данный синтаксис?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Есть. Это называется aggregate initializers. Доступно с C++20.

    Ну и, первая строка - это какой-то макрос, который, судя по контексту, разворачивается в декларацию переменной какого-то аггрегатного типа.
    Ответ написан
    1 комментарий
  • Как принять число любой длины?

    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 комментария