Задать вопрос
  • Как передавать Bitmap в функции? Как возвращать Bitmap?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Скорее всего не получается вернуть объект типа Bitmap, потому что его нельзя копировать. Попробуйте возвращать через std::move или возвращайте, например std::unique_ptr<gdiplus::Bitmap>.
    Ответ написан
    Комментировать
  • Как удалить Bitmap?

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

    hBitmap - да, удалять надо.
    В документации этот момент даже расписан:
    You are responsible for deleting the GDI bitmap and the GDI palette. However, you should not delete the GDI bitmap or the GDI palette until after the GDI+ Bitmap object is deleted or goes out of scope.


    Это делается через DeleteObject.
    Ответ написан
    Комментировать
  • Как правильно умножать восьмичные числа с плавающей точкой?

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