Задать вопрос
  • С: Объясните вторую часть задания?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Наверно, надо сгенерировать последовательность, написать функцию вычисления суммы цифр числа и используя ее найти элемент последовательности с наибольшей суммой.
    Ответ написан
  • Что означает traits_type::eof()?

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

    type_traits::eof() - возвращает код конца файла, для текущего параметра шаблона.

    Вся эта шаблонная магия взялась для того, чтобы можно было читать из файла или char, или wchar, или еще черт знает что, в зависимости от кодировки. Раз читаемые символы могут быть какими угодно, то и код конца файла нужен свой собственный для разных типов символов. Поэтому eof() является частью type_traits в streambuf.
    Ответ написан
    Комментировать
  • В чем проблема обхода в ширину и глубину?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    В BFS вы не проверяете, что вершина помечена, и всегда кладете вершину в очередь. А еще там в конце какой-то левый цикл ненужный. Поиск бесконечно циклится и съедает всю память. DFS, похоже, правильный (есть много претензий к стилю, правда).
    Ответ написан
  • Что использовать для формализации рассуждений?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Ну, вы уже правильно сказали, что это граф. Судя по всему вас интересуют компоненты связности в графе.
    Ответ написан
    2 комментария
  • Операции AND, OR, XOR Как проверить биты?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    X AND (2^1+2^2) ИЛИ X AND 230


    Слева же правильно написано, но вы как-то из 2+4 получили 230.

    Х AND (255–2^2–2^7) ИЛИ Х AND 221

    Тоже самое. Правильную операцию сделали, но както из 255-4-128 получили 221, хотя должно быть 123.
    И вместо X пишите A или B в заданиях. Дальше такие же ошибки.
    Ответ написан
  • Как вычислить 2 наименьших нечетных элемента массива в языке С?

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

    Потом (отдельно) найдите в массиве 2 наименьших элемента.

    Потом совместите 2 алгоритма.
    Ответ написан
    Комментировать
  • Как правильно использовать конструктор структуры?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вы передаете структуре в конструктор ее саму! Ее еще не создано, а вы ее передаете куда-то. Зачем вам вообще в структуре хранить ссылку на другую структуру? Это вы из питона, что ли взяли? В C++ не надо методам класса/структуры передавать указатель на нее, они средствами языка привязаны уже к экземпляру. Можно обращаться просто к членам структуры напрямую из методов. Или через this->, если есть конфликт имен.
    Ответ написан
    4 комментария
  • Как разбить данный массив?

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

    Потом пройдитесь по массиву, поддерживая счетчик открытых интервалов. Встретили "from" - увеличили счетчик. встретили "to" - уменьшили.

    Если изменили счетчик с 0 на 1, то в текущей дате начало отрезка в ответе. Если изменили с 1 на 0, то тут конец.

    Наверно, надо будет еще отрезки разбить по месяцам потом.

    Еще надо разобраться с тем, когда даты совпадают. Если в одну и ту же дату есть to и from - это же должно считаться одним отрезком? Тогда при сортировке ставьте "from" перед "to" на одну и ту же дату (В сравнении при равенстве дат сравнивайте еще и тип события).
    Ответ написан
    Комментировать
  • Как выполнить размещение k элементов из n?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Гуглите "алгоритм генерации размещений". Находится, например, это.

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

    Или можно сгенерировать размещения из {1,2,3,...N} а потом использовать эти числа в размещениях, как индексы символов. Надергайте из заданной строки символы по этим позициям и получите размещение из символов, а не чисел.
    Ответ написан
    Комментировать
  • Как он это "заметил"?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ну, это известная формула - количество пар среди n объектов. Для самого левого подходит n-1 правых концов. Для второго - их будет n-2. Для последнего - 0. Сумма (n-1)+(n-2)+...+1+0 = (n-1)n/2. Можно через сумму арифметической прогрессии получить.
    Ответ написан
    1 комментарий
  • Как вывести часть bitset-a?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    С битсетом можно работать, как с массивом. У него есть operator[]. Просто пройдитесь циклом в 3 итерации и выводите x[i].
    Ответ написан
    Комментировать
  • Найти позицию элемента в массиве?

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

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

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

    И надо еще доказать, почему не может быть последнее отражение когда поезда встретились. Допустим оба поезда и муха встретились в одной точке. А что было в момент предыдущего отражения? какое-то ненулевое расстояние между поездами. Но если с этого момента проиграть, то следующее отражение будет до момента встречи двух поездов. Опять противоречие.
    Ответ написан
    1 комментарий
  • Как реализовать "копирование" файла на C++?

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

    Используйте, например, ifstream и ofstream. Только нужно работать в бинарном режиме. Открывайте файлы, передавая std::ios::binary в конструкторы. Используйте read для чтения и write для записи. Там даже примеры есть вам релевантные в документации.

    Еще можно всякие итераторы использовать и std::copy.
    Ответ написан
  • Как мне сделать чтоб вибирались числа из промежутка между найменшим и найбольшем в двумерном масиве?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    if (max >= arr[i][j]) {
            max; 
          }
          else if (max <= arr[i][j]) {
            swap(max, arr[i][j]);
            maxii = i; maxjj = j;
          }


    ЧТО ТУТ ВООБЩЕ ПРОИСХОДИТ?
    Понятно, что пытались найти индекс максимума в массиве, но тут такой бред написан...

    Попробуйте сначала найти максимум тупо в одномерном массиве, а потом обобщить код на двумерный. Они только лишним циклом и отличаются же.

    А дальше, вот нашли вы ваши индексы... ну и гоните цикл от меньшего индекса до большего. Можно их местами поменять, если они не в том порядке идут.
    Ответ написан
    Комментировать
  • Почему так долго работает сортировка слиянием?

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

    mergeSort(a, temp, 0, mid);


    Надо сортировать часть с lo по mid. А не с 0.
    Ответ написан
    Комментировать
  • Как организовать сравнение переменной с элементом массива?

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

    Бинарным поиском находите в первом массиве индекс значения и выдаете ответ из второго массива по тому же индексу.

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

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

    Соответственно в парсере, если видите унарный минус перед скобками, то переводите скобки в нотацию, а потом дописываете ±.
    Ответ написан
    3 комментария
  • Как решить олимпиадную задачу python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Тут есть 2 подхода - дихотомия (бинарный поиск) по ответу, как написал Василий Банников: Вы бинарным поиском ищите значение r. Для каждого значения проверяете, а связен ли граф всех антен через обход в глубину (ребро межу двумя антеннами, если они видят друг друга напрямую для данного r).

    Другой вариант - через алгоритм построения остовного дерева Краскала. Сортируете все возможные ребра в графе (все расстояния между парами вершин). Потом добавляйте в изначально пустой граф ребра в этом порядке, пока он не станет связен (пока не построите остовное дерево). Последнее добавленное ребро и будет задавать r (половина длины ребра - ответ).
    Ответ написан
    Комментировать
  • После закрытия скомпилированной программы появляется ошибка Debug Assertion Failed?

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

    Вижу как минимум одно такое место. delete_reload_virus иногда удаляет virus, а потом что-то делает с r_vir. Но в качестве аргумента ей из viruspodMoving передается этот же самый r_vir.

    Какая-то каша у вас там творится. Одни и те же переменные использются как члены класса и передаются как указатели по всей программе. Там черт ногу сломит.
    Ответ написан