Задать вопрос
  • Можно ли вызвать деструктор void*?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Нет. Компилятору же надо знать, что там за деструктор вызывать. Что вы в void* на самом деле положили - он знать не может. Более того, там не только деструкторы, там и delete у указателей вызван не будет. Руками придется сначала привести к правильному типу и потом отчистить память (что вызовет деструктор).
    Ответ написан
  • Как задать условие для цикла?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    По уму, надо выделять последовательность нулей в цикле и там смотреть, а не с начала ли дня она идет и не до конца ли дня.

    Но можно проще. Считайте вообще все последовательности нулей. до какой-то пары (это значит сейчас 0 - а следующаяя ячейка не ноль.). Но так посчитаются недо-окна перед первыми парами. Вы можете эти недо-окна подсчитать. Это просто те дни, в которых в начале стоит 0. Но тут, вы правильно заметили, проблема. День в котором одни нули посчитается недо-окном и вычтется, но ничего к ответу не прибавит. Поэтому вам надо отдельно прибавить количество дней из одних только нулей.
    Ответ написан
    Комментировать
  • Как посчитать число цифр в скобках, предварительно проверенных на сбалансированность?

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

    Если счетчик открытых скобок стал где-то отрицательным, или в конеце цикла он не ноль - то строка не сбалансирована.
    Ответ написан
    5 комментариев
  • Как оптимизировать данный код?

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

    Это известная, очень сложная (NP-сложная) задача об упаковке.

    Для сотен тысяч входных списков вы оптимальное по количеству кусков в ответе решение не найдете за все время до тепловой смерти вселенной. Всякие аппроксимации, вроде вашего жадного алгоритма, могут найти лишь какое-то хорошее, но не лучшее разбиение. В частности, у вас используется Next-Fit аппроксимация - вы в итоге можете выдать в 2 раза больше кусков в ответе, чем можно было бы. Есть более сложные алгоритмы, которые, например, гарантируют ухудшение максимум в 1.7 раза.

    Соглашусь с Dr. Bacon, через yield код вашего решения может быть чуть красивее, но я не совсем понимаю, что в вашей реализации вам так "не красиво". Хотя я не питонист.

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

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

    Более простое но и более медленное решение (за O(n^2)) - считайте полиномиальный хеш всех подстрок и храните в хешмапе минимальный индекс для каждого хеша. Оптять же, как только встретили подстроку, которую уже видели и ее первый индекс такой, что нет пересечения с текущей строкой - вы нашли ответ.

    Еще за O(n^2) же есть решение через динамическое программирование: считайте F(i,j) - максимальная длина совпадающих строк, начинающихся с символов i и j (F(i,j) = 1 + F(i+1, j+1), если s[i] == s[j] и 0 иначе). Потом для каждой пары начал берите минимум из f(i,j), abs(j-i) - это и будет максимальная длина непересекающихся фрагментов с этих индексов. Если где-то нашли больше 5 - это ответ.

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    У вас одно уравнение с двумя неизвестными (x и y).
    Что вы с ним ни делайте, оно так и останется одно, с двумя неизвестными. Оно дает вам какую-то связь неизвестных, но, само по себе, не даст их найти.

    Уравнение линейное.
    Вы или можете его привести или к виду x= Ay+B (A=-p, B=zp-n) или к виду y=Cx+D (C=-1/p, D=z-n/p)

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Комментарии в коде вроде //4 значение по адресу однозначно говорят, в чем проблема. Вы хотите работать с четверкой чисел, а в строке их у вас всего 2.
    Ответ написан
  • Будет ли работать бинарный поиск, если в массиве есть пробелы?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Будет. Бинарному поиску главное, чтобы числа в массиве не убывали. Даже если там числа больше предыдущего не только на 1.
    Ответ написан
    Комментировать
  • Как работает алгоритм перебора перестановок (рекурсия)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Перебирается число, которого еще нет в массиве. Ставится на следеющее место и рекурсивно запускается для каждого варианта.
    Ответ написан
    Комментировать
  • Можно ли как то найти?

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Подсказка: в c++ в цикле for не обязательно использовать i++. Можно, например, i+=10.
    Ответ написан
    Комментировать
  • Не работает код C++?

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

    Ну и вывод в цикле будет весьма спамный.
    Ответ написан
    Комментировать
  • Как рассчитать пройденное расстояние, которое тело пройдёт при разгоне с 0 до 100 км/час?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Ускорение: a=v/t
    Расстояние: s=at^2/2

    t= 11 сек
    v= 100 км/ч = 27.777(7) м/с

    Подставьте сами
    Ответ написан
    4 комментария
  • Тип с точностью до 4 знаков C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Есть. Называется int. Вам надо хранить количество десятитысячных в числе. Иными словами, вы вместо x храните в int x*10000. При выводе делите на 10000 (и установите выводить 4 знака).

    Такие числа можно просто складывать и вычитать. При умножении надо будет результат поделить нацело на 10000 (или округлить к ближайшему, делящемуся на 10000 и потом отбросить 4 нуля). При делении - наоборот. Надо сначала домножить числитель на 10000, а потом поделить нацело на знаменатель (возможно стоит подумать об округлении к ближайшему целому).

    Upd: И вообще, раз уж разговор о C++, то можно реализовать свой класс. Там можно даже отдельно хранить целую часть и 4 знака после запятой. Если вам встроенной точности int/int64_t не хватает. Все математические операции можно переопределить и работать, как со встроенным типом. Вообще, по-умному, это называется fixed point numbers.
    Ответ написан
    Комментировать
  • Как сделать поворот фигуры?

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

    Так, поворот против часовой стрелке вдоль оси Z, меняяет местами X, Y и делает меняет знак у X, т.е. X' = -Y, Y' = X, Z' = Z. Вам надо все тройки вот таким побразом поизменять. Поворот по часовой стрелки вдоль Z делает наоборот. Опять же меняет X и Y и меняет знак Y.

    Повороты вдоль других осей придумайте сами. Меняются местами две другие оси, и какая-то из них меняет знак. Представьте, куда двигаются (1,0,0), (0, 1, 0) и (0, 0, 1), что бы понять правила.

    При реализации только аккуратно делайте. Если помене на месте, то надо именно swap делать, ведь если выполнить x=-y; y=x, то у вас изначальная x координата затрется в первом выражении и потеряется навсегда.
    Ответ написан
    Комментировать
  • Как реализовать Алгоритм Решето Эратосфена от определенного числа, до данного?

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

    const int BE = 900000000;
    const int N = 1000000000;
    
    std::vector<int> small_primes;
    
    bool DivisibleBySmallPrimes(int x) {
    	for (int i = 0; i < (int)small_primes.size() && small_primes[i]*small_primes[i] <= x; ++i) {
    		if (x % small_primes[i] == 0) return true;
    	}
    	return false;
    }
    
    void ComputeSmallPrimes() {
    	int n = sqrt(N);
    	for (int i = 2; i <= n; ++i) {
    		if (!DivisibleBySmallPrimes(i)) {
    			small_primes.push_back(i);
    		}
    	}
    }
    
    void ComputeSieve() {
    	ComputeSmallPrimes()
    	std::vector<bool> sieve(N-BE+1);
    	std::vector<int> primes;
    	for (auto &x : small_primes) {
    		int i = (BE-1) - (BE-1) % x + x;
    		while (i <= N) {
    			sieve[i-BE] = true;
    			i += x;
    		}
    	}
    	for (int i = BE; i <= N; ++i) {
    		if(!sieve[i-BE]) {
    			primes.push_back(i);
    		}
    	}
    }


    upd:
    ComputeSmallPrimes можно переписать простым решетом - будет еще быстрее.
    Ответ написан
    Комментировать
  • Как написать на С++?

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

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

    Например, DirectShow или MediaFoundation.

    MediaFoundation поновее, побыстрее, поэффективнее и чуть поудобнее. Но криворукие разработчики драйверов его не всегда хорошо поддерживают. Всякие, особенно интегированные в лаптопах, камеры с ним глючат или не работают вообще. Плюс всякие виртуальные камеры, типа OBS не видны через MediaFoundation, потому что разработчикам влом по-нормальному реализовывать виртуальную камеру. Ну и оно только с windows 7 доступно.

    Если вы не планируете открывать камеру, а вам надо только информацию о ней собрать, или вы работаете с определенным устройством, то MediaFoundation вам подойдет лучше.

    Иначе смотрите DirectShow.

    Можно найти много примеров кода в интернете.
    Ответ написан
    2 комментария
  • Как изменить уравнения?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    s/i=delta/gamma

    Вторую часть не совсем понял, вы хотите подставить s из первого уравнения во второе и обособить i?

    Тогда Result1= (d/i+1)*gamma/delta

    Upd: ответ на отредактированный вопрос - никак. i всегда будет входить в выражение в степени -1.
    Ответ написан
  • В строке все элементы в десятичной системе счисления заменить в шестнадцатеричной системе?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Тут есть 5 подзадач:
    1) разбить строку на слова
    2) определить по слову, является ли оно числом в десятичной системе счисления
    3) Перевести слово в число
    4) перевести число из десятичной системы счисления в 16-ричную
    5) Записать число в 16-ричной системе в строку

    1,3,4 и 5 - стандартны и гуглятся.
    2 - подсказка: проверьте, что слово состоит только из символов '0'-'9' и не начинается с '0'. По идее, надо бы еще разрешить слово "0", но ноль, он и в 16-ричной системе будет ноль, поэтому такое слово можно не учитывать в вашей задаче. Символы 0..9 имеют коды ascii подряд, поэтому в программе достаточно записать с >= '0' && c <= '9'.
    Ответ написан
    Комментировать