Задать вопрос
  • How to fix packing error in ue5?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Try doing what the error messages are telling you:

    Detected compiler newer than Visual Studio 2022, please update min version checking in WindowsPlatformCompilerSetup.h


    Or install the Visual Studio 2022 instead of what you have.
    Ответ написан
  • Почему в c++ еще нету Null-Conditional Operator?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это не достаточно частая операция в С++, чтобы срочно надо было вводить новый оператор в синтаксис. Комитет занят более интересными вещами на годы вперед.
    Ответ написан
    3 комментария
  • На чём создать прогу для обработки больших данных?

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

    Быстрее, конечно, работать будет на C++/rust каком-нибудь, но обработка csv может быть легче реализованна на питоне.
    Ответ написан
  • Есть ли разница между *p++ и p++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Разница как бы есть. В одном случае у вас *(p++), а в другом просто p++. И то и другое сдвинет указатель p на одну ячейку вправо, т.е. код имеет ровно тот же результат. Но в случае с * вы еще и адрес p, который там был до увеличения, разименуете, т.е. получите доступ. Но просто такое выражение, где вы его разименовываете и ничего с ним не делаете не имеет смысла. Его можно использовать, если вы со значением что-то делаете, например:
    void Copy(char *src, char *dst) {
        while (*src) {
          *dst++ = *src++;
        }
        *dst = '\0';
      }


    Тут вы значение по адресу src берете и записываете в адрес dst. Но из-за ++ оба указатлея сдвинутся. Получается копирование сишной строки.

    Но делать просто *p++; смысла никакого нет. Это примерно то же что и:
    int i;
    i;

    Вот выражение `i;` - оно как бы получает доступ к i, но со значением ничего не делает. Это странный и бесполезный код.

    Так что * у вас там явно лишняя.
    Ответ написан
    Комментировать
  • Как скомпилировать экзешник из гитхаба?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    В ошибке же написано "Unexpected compiler version, expected CUDA 10.1 Update 2 or newer."

    Перевод на русский - поставьте CUDA версии 10.1 update 2 или новее.
    Ответ написан
    3 комментария
  • Как "выпрямить" кольцевой буфер c ограниченной доп.памятью?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ваша задача - сделать циклический сдвиг массива на k позиций влево на месте, с O(1) дополнительной памяти.
    Вот код:
    void ShiftLeft(std::vector<int> &a, int k) {
      int n = a.size();
      int cycles = std::gcd(n, k);
      for (int start = 0; start < cycles; ++start) {
        int tmp = a[start];
        int i = start;
        while (true) {
          int next = i + k;
          if (next >= n) next -= n;
          if (next == start) break;
          a[i] = a[next];
          i = next;
        }
        a[i] = tmp;
      }
    }


    Работает это так: на место элемента вставет элемент на k позиций правее. Возьмем первый элемент, запомним его в tmp, поставим на его место тот, кто там должен быть. Освободилось место, поставим на него опять того, кто там должен быть и так далее. Рано или поздно мы вернемся к первому элементу. Но там уже стоит второй. Тут можно выйти из цикла и поставить на нужное место тот, кого мы сохранили в tmp. Но мы могли обойти не весь массив, как, например в случае n=6, k=2. Начав с 0 мы тут подвинем элементы 0,2,4, но не 1,3,5. Всего будет циклов gcd(n, k), и они все идут со сдвигом 1. Поэтому можно начинать с каждого из нескольких первых элементов.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Инверсия тут - это из комбинаторики. Инверсия - это когда 2 элемента не в том порядке. Количество инверсий - это сколько пар элементов стоят не так. В массиве (1,2,3,4) инверсий 0. В массиве (1,4,3,2) инверсий 3: 4 и 3, 4 и 2, 3 и 2 - вот эти 3 пары идут по убыванию, вместо нормального порядка. Оставшиеся 3 пары стоят как надо.
    Ответ написан
  • Можно ли как-то короче доказать этот факт?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    После пункта 4 вам надо лишь доказать, что найденные xi yi будут всеми решениями системы. Допустим есть какое-то еще решение {x' y'} не среди xi, yi. Но, раз оно удовлетворяет f(x',y')=0, то x'=f'(y'). Еще оно удовлетворяет g(x',y')=0, а значит и g(f(y'),y') = 0, т.е. вы бы это y' нашли среди ваших yi, но мы предположили обратное.
    Ответ написан
  • Как сделать безопасную многопоточную очередь?

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

    Если вы гонитесь за эффективностью и параллельностью, то вам лучше написать lock-free структуру данных. Гуглите эти ключевые слова. Но это очень сложно.

    Еще, как вариант, можно физически разбить очередь на 2 куска. Один для записи, другой для чтения. Т.е. у вас 2 очереди, каждая со своим локом. При доступе к голове вы блокируете мьютекс на чтение и читаете из очереди на чтение. При доступе к хвосту - на запись. Записывать тривиально - просто лочте мьютекс на запись и добавляйте элемент в очередь на запись. При чтении лочте очередь на чтение и читайте из нее. Но, если вы выяснили, что очередь на чтение оказалась пуста, то надо залочить еще и очередь на запись и поменять их местами (т.е. перекинуть всю очередь записи в чтение). И потом вернуть голову этой очереди.

    Такой подход позволит более-менее параллелить чтение и запись, особенно, если очередь часто не пуста.

    Лочить только один эелемент с каждого конца сложно - там очень много случаев. Лоча 2 половины отдельно вы можете не думать о другой большую часть времени.
    Ответ написан
    5 комментариев
  • Поиск куда можно добраться по графу за время?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если граф не взвешанный, то запустите обычный bfs, только не кладте в очередь вершины с расчтоянием больше ограничения. Если граф взвешанный, то запустите обычного Дейкстру, только остановитесь, когда зафиксируете вершину с раччтоянием больше допустимого.
    Ответ написан
    Комментировать
  • Знаю что данная задача решается методом двух указателей, но не понимаю почему мы двигаем указатель с меньшей высотой в сторону противоположного?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Рассмотрите один столбик (допустим, номер i). Какой высоты в нем может быть вода? Обозначим за x. Она не должна выливаться ни слева ни справа. Значит, с обеих сторон должен быть столбик с высотой хотя бы x. Раз есть хотя бы один, то максимум точно должен быть хотя бы x. Отсюда x <= max(h[0..i-1]) и x <= max(h[i+1..n-1]) Значит высота воды в i-ом столбике: min(max(h[0..i-1]), max(h[i+1..n-1])). Уже можно просто вот это подсчитать за 2 прохода и получить решение. Ну, только не забыть что там надо max(x, h[i])-h[i] к ответу прибавить, ведь если текущий столбик слишком высокий, то вся вода с него стечет.

    Но можно думать дальше. Давайте обрабатывать не все столбики подряд, а посмотрим с краев. С крайних столбиков все, понятно, вытекает наружу. Пусть крайний левый меньше. Рассмотрим второй столбик слева. Мы уже знаем max(h[0..i-1]) в нем - это один левый столбик. И оно точно меньше max(h[i+1..n-1]), потому что справа уже есть крайний столбик, который выше самого левого. Мы незнаем точное значение max(h[i+1..n-1]), но мы знаем что max(h[i+1..n-1]) >= h[n-1] >= h[0] = max(h[0..i-1]). Вот мы знаем высоту воды в столбике 1, мы же берем минимум из двух значений. Даже если мы не знаем максимум справа, мы знаем, что он точно больше максимума слева и в ответе не участвует.

    Вот мы и обработали второй столбик. Теперь перейдем к третьему. При этом можно первые 2 столбика объеденить в один высоты max(h[0], h[1]). Это и есть сдвиг указателя, только при этом мы смотрим не на сам столбик, а аккумулируем максимумы с краев.

    Но, если бы мы смотрели на второй справа столбик, рядом с большим их двух крайних, то мы не могли бы сразу сказать, а какая там высота воды. Мы в нем знаем max(h[i+1..n-1]) - высота последнего столбика. Но какое в нем max(h[0..i-1]) мы не знаем и не можем сказать, больше ли оно или нет, а значит, не можем посчитать x.
    Ответ написан
    1 комментарий
  • Разрезание многоугольника горизонтальными линиями. Алгоритм?

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

    Самая концептуально простая реализация будет, если сделать функцию для отсечения группы многоугольников полуплоскостью. Прямоугольник ваш - это 4 полуплоскости: 2 вертикальные и 2 горизонтальные. Пересечение с полуплоскостью проще - там тупо прямая же одна. Вот пресеките многоугольник с первой, полученные ответ со второй, потом что осталось с третьей и потом с четвертой полуплоскостью.

    Удобно хранить множество точек и для каждой - указатель на сделующую в обходе многоугольника (ориентированного так, что слева от отрезка внутренность многоугольника). В таком виде входные данные, в таком виде будет и ответ.

    Точки будем помечать, как обработанные.

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

    Потом надо будет все точки пересечения соединить в порядке вдоль прямой парами (смотрите так, чтобы удаляемая область была справа от направления движения). Их будет четное количество.

    Вот у вас все оставшиеся точки образуют многоугольники, если идити по указателям на следующую. Правада, они в массиве могут идти вперемешку, а не подряд. В конце вам может понадобится их сгруппировать, но это делается похожим обходом: помечайте точки обработанными, берите любую не обработанную и идите от нее по указателям, пока не вернетесь в нее же, помечая все точки как обработанные и добавляя в ответкак часть одного многоугольника. Это можно сделать после того, как пересечете со всеми 4 полуплоскостями.

    Удобно прямую хранить в виде Ax+By+C=0. И знак подобрать так, что точки внутри хорошей области, если их подставить в это уравнение дают положительные значения (а точки снаружи - будут отрицательные). Соответственно, проверка, что с точки можно начать обход - просто посмотреть на знак. Проверка, что есть пересечение - конец отрезка дает отрицательный знак (а потом - положительный). Точки удобно хранить в виде массива координат и массива номеров следующей точки в обходе. Никаких сишных указателей - номера следующей точки в массиве. Сортировать точки пересечения надо будет по значению Ay-Bx.

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

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Угол 0 куда смотрит? Куда смотрит 90 градусов? Обычно считают, что 0 смотрит строго враво, а 90 - вверх.

    Шаг 1. Вам неважно, где именно находятся башня и цель, важно их относительное положение, поэтому посчитайте dx=x2-x1, dy = y2-y1

    Шаг 2. Подставьте в какую-нибудь обратную тригонометрическую функцию, например arctan(dy/dx). Тут правда незадача, если dx=0, то надо смотреть на знак dy и выдавать sign(dy)*90. Еще проблема, что arctan вам вернет значение от -90 до 90 всегда. Если dx отрицательно, то надо прибавить 180.
    Ответ написан
    2 комментария
  • Всегда ли DP можно представить в виде DAG?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Тут вопрос определений. Что считать "представить в виде DAG".

    В ДП можно составить граф зависимостей: какие состояния участвуют в вычислении каждого. Это будет DAG. Иначе у вас надо вычислять значения через самих себя и у вас уже не рекуррентные соотношения, а система уравнений.
    В некоторых задачах эту систему уравнений можно решать иерархически, по частям, отдельно в каждой компоненте сильной связности. Это немного напоминает ДП, но им не является. Суть ДП в том, что у вас рекуррентные формулы. Это некий более общий алгоритм.

    Если интерпретировать вопрос как: можно ли сформулировать задачу в виде "дан граф, подсчитать вот такую функцию в каждой вершине", то тут можно натянтуть сову на глобус, придраться к деталям и сказать, что нельзя. Именно это и говорится в SO.

    Потому что иногда рекуррентные формулы не симметричные и вам надо, например, одно значение прибавить, другое вычесть. Это не всегда просто определить исключительно в терминах графа. Нельзя сказать что-то вроде "сложить значение во всех вершинах, куда ведут ребра". Но если добавить в этот граф пометки на ребрах или параметры состояний в вершинах, то можно задать нужную функцию (вроде: взять значение для вершины, в которую ведет ребро с пометкой 1 и вычесть значение из вершины, куда ведет ребро с пометкой 2).

    Но эти помеченные графы все еще будут DAG.
    Ответ написан
    3 комментария
  • Объясните, пожалуйста, смысл такого фрагмента кода класса _Iosb файла xiosbase?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Правильно ли понимаю, что после присвоения _Fmtflags skipws = (_Fmtflags)_IOSskipws; _IOSskipws становится челном перечисления _Fmtflags ?


    Нет, сначала препроцессор заменит _IOSskipws на 0x0001, потом skipws инициализируется 0x0001.

    Зачем так сделано? Может, кто-то очень жестко следует правилу не использовать магические числа в коде. Все константы должны быть как-то определены заранее. Видимо, в стиле, принятом тут, константы заводят через define.

    Или IOSskipws используется в инициализации каких-то еще констант в этом или другом классе и тогда имеет смысл заводить его отдельно.

    Оказывают ли поля _Fmtmask = 0xffff, _Fmtzero = 0 перечисления _Fmtflags, какое либо влияние на поля _IOSskipws


    _IOSskipws - это вообще не поле, это символ, заменяемый препроцессором на 0x0001. Он с точки зрения С++ вообще не существует.
    Ответ написан
    Комментировать
  • Не работает кнопка сервис. как исправить?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    break; в коде все портит. Выполняется первая проверка, не срабатывает, наверно, потому что currentState не тот. А может, потому что у вас там еще break между уловными проверками расставлены. До проверки на BUTTON_ID_CLOSE_SERVICE код никогда не доходит.

    Break должен быть один раз в конце case блока, чтобы управление не перешло на следующий case. Switch же просто переносит управление на соответствующий case и все. Он не отключает как-то куски кода в других альтернативах.
    Ответ написан
  • Почему код выкидывает исключение переполнение стека?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    У вас массив внутри класса, класс - локальная переменная. Получается массив на стеке. На 4 миллиона ячеек. Но стек ограничен и вот он переполняется. Стандартного размера не хватает. Надо поднять размер стека опциями линкера.

    Или экземпляр класса создавайте в куче, через new, и храните в unique_ptr.

    А по коду: не используйте эту сишную арифметику указателей. У вас двумерный массив, вы и обращайтесь везде через 2 индекса в квадратных скобках. Так понятнее код будет.
    Ответ написан
    Комментировать
  • Почему не удаётся освободить память в деструкторе?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема вот в этой строчке:
    int get_num_from_BigInteger(BigInteger big_int){

    Тут у вас идет передача по значению. У вас создается новая BigInteger переменная, со значением переданной. Поскольку вы конструктор копирования нигде не определили, компилятор сделал его вам сам, и там он тупо копирует все данные класса, включая указатель arr.
    В итоге у вас получается два экземпляра класса, в каждом из которых указатель на один и тот же массив. Потом каждый из двух экземпляров в деструкторе вызовет free для одного и того же указатенля, вот и получается двойной free и креш.

    Вам надо руководствоватся правилом трех(пяти). Доопределите конструктор копирования. Вообще, вам бы стоило его запретить (= delete;), ибо копировать такие большие числа - это плохо. А в функции ваши передавайте BigInteger по константной ссылке.

    Ну и в других функциях та же самая поблема.

    И еще, в C++ не стоит использовать malloc/free, используйте new/delete. А еще лучше, используйте std::vector.
    Ответ написан
    Комментировать
  • Почему при полностью идентичном содержимом файлов (*.js, *.php, *.css) они могут иметь разный вес/размер?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Многие платформы поддерживают метаданные для файлов. В винде они называются потоками (file streams). Их не видно, если просто открыть файл, но всякие программы знают, как туда залезть и что-то там посмотреть. Например, все браузеры при скачивании файлов из интернета делают в этих потоках пометку, что файл-то скачан. И винда потом при попытке открыть такой экзешник обычно выдает предупреждение: "Ахтунг, файл из интернета, точно хотите открыть?"

    В эти потоки можно много чего запихать. Сами по себе данные там никак не могут заразить компьютер, но какой-нибудь вредоносный загрузчик вполне может данные оттуда достать и запустить. Так что это может быть скрытая полезная нагрузка вирусни, и какой-то один из файлов содержит код распаковки.

    На линуксе похожая штука точно есть, но я не помню, как оно называется.

    Еще варант: не ошиблись ли вы с подсчетом размеров файлов? Может вы килобайты с кибибайтами перепутали?

    А гит скорее всего заметил измененные даты на файлах, но изменений в самих файлах не нашел. И да, гит эти потоки игнорирует.
    Ответ написан
    2 комментария
  • Более формальный вывод из доказательства по принципу наименьшего числа?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Нет, эти рассуждения не нужны, вы перемудрили немного. Вы предположили, что во множестве есть минимальный элемент, но получили, что во множестве есть меньший этого минимума элемент. Противоречие. Ибо все остальные элементы множества больше минимального (по определению минимума). Все. Отсюда следуюет что во множестве нет минимального элемента.

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

    Есть еще тонкий момент: рассуждения получающие меньший элемент заданного иногда нельзя применить ко всем числам. Например, если вы работаете с целыми положительными, а предположенный минимальный у вас 1, то из 1 вы меньшее число никак не получите. Поэтому надо сначала проверить, принадлежит ли 1 к множеству и потом предполагать существование минимального элемента > 1.
    Ответ написан
    1 комментарий