• Как правильно умножать восьмичные числа с плавающей точкой?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    В столбик. Точно так же как обычные десятичные числа, только помните, что цифры 8 нет. Если получилось больше 7, все остальное, поделенное на 8 переносится дальше.
    Ответ написан
    Комментировать
  • Почему мой код не проходит по времени?

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

    Сначала решетом эратосфена найдите для каждого числа минимальный простой делитель. У меня даже статья про этот алгоритм есть с кодом и объяснением.

    Потом, решение за O(n log n) - можно быстро найти все простые множители каждого числа используя массив с предущего шага. Считайте степени простых множителей и перемножайте их +1. Так 2^2*3^1 имеет (2+1)(1+1) = 3*2 = 6 делителей (включая 1 и 12. Если они не нужны, вычтите 1-2 в конце).

    Но можно сделать еще быстрее. Фактически применив динамическое программирование. Во втором массиве посчитайте степень минимального простого делителя для каждого числа. Если мнимальный делитель (p[i]) для i равен мнимальному для i/p[i], то степень для i будет 1 + степень для i/p[i]. Иначе она будет 1. Так же посчитайте для каждого числа что там останется, если выкинуть все вхождения минимального делителя. Потом в другом массиве посчитайте для каждого числа количество делителей - это ответ для числа без всех вхождений минимального, умноженный на количество этих минимальных делителей +1. Ну а потом по этому массиву считайте сумму. Это будет работать за O(n).
    Ответ написан
  • Как заполнить матрицу из массива?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Элемент в строке i в столбце j (считая с 0) в линейном массиве будет иметь номер i*n+j (или там на m надо вместо m умножать. Там должно быть количество столбцов).

    Соответственно, программа должна двумя вложенными циклами присваивать в ячейку [i][j] вот тот вот элемент из массива.
    Ответ написан
    3 комментария
  • Почему не отсеиваются нули при сравнении 0 < 0?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    array[index + 1] ? item < array[index + 1] : true Что эта конструкция делает, можете объяснить? Ошибка в ней.
    Ответ написан
    5 комментариев
  • Нужно ли писать суффиксы литералов?

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

    Вот когда вы константы передаете в какие-то перегруженные функции, где имеет значение unsigned ли ей передан или signed, или есть разница между float и double, то тогда - да, надо писать.
    Ответ написан
    4 комментария
  • Удалить из ряда элементы ,как?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Например, вот так:
    def GenerateAll(source, rep):
      for comb in itertools.combinations(range(len(source)), len(source)-len(rep)):
        s = list()
        prev = 0
        for (i, j) in enumerate(comb):
          s.append(source[j]);
        yield "".join(s)


    Обратите внимание, перебираем не сочетания из удаляемых позиций, а из 22 оставляемых (кстати, у вас числа не бьются, 48+22 = 60 != 64). Тут порядок в ответе будет обратный (первая строка будет "xxxxxx...xxxx12..." а не "12..xxx..xx". Если нужен тот же порядок, то будет чуть сложнее:
    def GenerateAll(source, rep):
      for comb in itertools.combinations(range(len(source)), len(rep)):
        s = list()
        prev = 0
        last = 0
        for (i, j) in enumerate(comb):
          while (last < j):
              s.append(source[last]);
              last += 1
          last += 1
        while (last < len(source)):
              s.append(source[last]);
              last += 1
        yield "".join(s)


    Это не самое питонистое решение, возможно в какой-то библиотеке уже есть готовая функция, которая вырезает из строки символы по индексам.
    Ответ написан
    1 комментарий
  • Теоретически, что будет если дать процессору инструкцию поделить на ноль без механизмов обработки?

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

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

    Но процессор не вычитает кучу раз подряд, ведь там двоичная система счисления. Разряд вычисляется проверкой на переполнение при одном вычитании со сдвигом, а результат идет дальше. Вот лекция о том, как устроена схема делителя.

    При вычитании нуля со сдвигом там никогда переполнения быть не будет, поэтому все биты ответа получатся равными 1.

    В итоге оно скорее всего выдаст неправильный результат. Что-то вроде 2^31-1 для любого делимого.

    Правда, если Intel/Amd/etc. нагородили каких-то оптимизаций или как-то усложнили схему, то результат может быть другим.
    Ответ написан
    Комментировать
  • Можно ли обратиться к полю дочернего класса через указатель на базовый?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Если вы точно знаете, что это именно экземпляр дочернего класса, то можно скастовать к дочернему через dynamic_cast, или вернуть скастованный указатель на дочерний класс через какой-нибудь виртуальный метод Derived* GetDerived(). Без какого-либо преобразования к дочернему классу - не получится. Не упоминать этот дочерний класс - тоже. Только если вы это поле/метод выведите в виртуальный метод базового класса.
    Ответ написан
    Комментировать
  • Как находить лучший способ решение задачи на олимпиадном программировании?

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

    А так - на до сначала построить математическую модель задачи. Понять, на что эта модель похожа. Может, тут граф нарисовать можно? Какие алгоритмы на графы вы вообще знаете? Применимы ли они тут? Или это строка. Какие есть алгоритмы на строки? Смотрите еще ограничения. По ним обчно понятно, что тут нужно что-то за O(n), или за O(n log n) написать. Множество применымых алгоритмов еще больше уменьшается.

    В задачах на оптимальность чего-то помогает рассуждение "рассмотрим ответ. Какие у него можно заметить свойства. Можно ли какой-то ответ немного поменять, не ухудшая его?" Так вы получите какое-то свойство, которое можно уже применять для построения ответа. Например в задачах на жадность так можно понять, что надо отсрортировать что-то.

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Вообще, вот алгоритм для произвольных слов: https://e-maxx.ru/algo/longest_increasing_subseq_log

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

    Какие у вас там ограничения: длины строк и количество повторений?
    Ответ написан
  • Какие темы самые важные для олимпиадного программировании в книге Кормена «Алгоритмы. Построение и анализ»?

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

    Менее важные, но встречающиеся темы:
    Глава 30. Полиномы и быстрое преобразование Фурье
    Глава 31. Теоретико-числовые алгоритмы
    Глава 32. Поиск подстрок
    Глава 33. Вычислительная геометрия

    Но лучше прочитать, таки, всю книгу. Вправляет мозги, учит строить математические модели задач, что в олимпиадах очень важно.
    Ответ написан
    6 комментариев
  • Как вернуть до пяти типов из одной функции?

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Раз вы просто копируете через memcpy, то никаких проблем не должно быть.
    А еще, вы уверены что std::swap сам эту оптимизацию уже не применяет? Зачем вы какие-то свои велосипеды строите?
    Ответ написан
  • Как вычислить число итераций алгоритма Евклида через вычитание?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Алгоритм через деление с остатоком - это всего-лишь оптимизация алгоритма через вычитание. Просто куча вычитаний делается скопом. Так же можно их все и подсчитать. Просто прибавляйте каждый раз не 1, а сколько там раз меньшее число в большее помещается. Типа answer += b/a
    Ответ написан
  • Нужно ли переводить из градусов в радианы для правильного направления стрелки?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Да, нужно перевести скорость в радианы. Так, чтобы 0 было pi/2 радиан (направление вверх), а -200 - это 4/3pi. И радианы при увеличении скорости уменьшаются.

    Поскольку все линейно, то фрмула такая: alpha = pi/2 - speed*5/1200.0

    Что такое angleValueTransformer я не знаю, но если ему задаются отрезки углов и значений, которые оно линейно преобразует в друг друга, то углы должны быть от 240 до -60, что соответствует скоростям от -200 до 200. Ну, или углы от 4/3pi до -pi/3, если вы значение сразу в синусы/косинусы передаете, не переводя из градусов в радианы.

    И, кстати, развертка будет не 310, а 300 градусов от -200 до 200. Иначе скорость 0 не будет вертикально вверх.
    Ответ написан
  • Как найти все способы представить число в виде произведения чисел Фибоначчи?

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

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

    Можно будет чуть ускорить, используя какой-нибудь ассоциативный массив для запоминания ответов. Его можно даже переиспользовать среди всех тестов.
    Ответ написан
    5 комментариев
  • Bitmap, hBitmap как загрузить сохраненный bmp?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Надо воспользоваться Gdiplus::Bitmap. Он умеет читать из файла.
    Дальше из него можно получить HBITMAP, если надо. А можно и дальше Gdiplus::Bitmap передавать.

    HBITMAP LoadHbitmapFromFile(const std::wstring& filename)
    {
        Gdiplus::Bitmap* bitmap = Gdiplus::Bitmap::FromFile(filename.c_str(), false);
        HBITMAP result = NULL;
        if (bitmap)
        {
            bitmap->GetHBITMAP(Gdiplus::Color(255, 255, 255), &result);
            delete bitmap;
        }
        return result;
    }
    Ответ написан
    5 комментариев
  • Не работает простой код хотя он правильный в чем может быть проблема?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вы уверены? У меня точно такой же код выводит числа от 1 до 10. Скорее всего вы программу нескомпилировали, или запускаете какой-то другой код по ошибке.
    Ответ написан
    1 комментарий
  • Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

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

    Every value of pointer type is one of the following:
    * a pointer to an object or function (in which case the pointer is said to point to the object or function), or
    * a pointer past the end of an object, or
    * the null pointer value for that type, or
    * an invalid pointer value.


    Т.е. arr у вас, вообще-то, invalid pointer value перед циклом.

    Плюс там же написано:
    Any other use of an invalid pointer value has implementation-defined behavior.


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

    Edit: немного не то написал. Так делать "не рекомендуется", а не "небезопасно". Оно генерирует непереносимый код. Если у вас на конкретном компиляторе с конкретными ключами работает, то, в общем-то, можно использовать. Но лучше не надо.
    Ответ написан
    5 комментариев
  • Vector не обновляется?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    (Исходя из обсуждения в комментариях)
    Возможно, проблема с параллельным кодом. Какой-то код где-то изменяет вектор. Если не очевидно, где оно все перезаписывается, то помните, что добавление элементов вектор может вызвать увеличение внутреннего буфера и копирование всех элементов. Поэтому даже какой-то код, просто добавляющий новые элементы в вектор, может вызвать наблюдаемый эффект необъяснимой перезаписи объекта в векторе на предыдущее значение. Вообще, надо бы защищать вектор от параллельного доступа разными потоками всякими мютексами и критическими секциями. Ну нет, так поменяйте его хотя бы на list. тогда добавление новых элементов и изменение значений где-то не будут вызывать data race. Но тогда надо алгоритмы менять, ибо обращение по индексу - долгая операция.
    Ответ написан
    Комментировать