Задать вопрос
  • Расширенный алгоритм Евклида с усеченными остатками?

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

    Вы там поддерживаете инвариант x_i*a+y_i*b = r_i

    Сответсвтенно, вам надо пересчитать x_cur и у_cur вместе с изменением r_cur.

    У вас есть x_prev*a+y_prev*b = r_prev и x_cur*a+y_cur*b = r_cur. Вам надо составить линейную комбинацию r_prev - r_cur. Ну вычтите одно уравнение из другого и все.

    Соответственно вам надо сделать вот это при применении вашего усечения:
    x_cur = x_prev - x_cur
    y_cur = y_prev - y_cur
    Ответ написан
  • Как решать задачу с графом?

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

    Можно применять тот же прием, что и в задаче коммивояжора - расслоите граф на 2^n слоев. Пуст у вас n вершин в изначальном графе. В новом графе каждая вершина соответсвует подмножеству комнат и одной комнате. Фактически, вершина обозначает, какие комнаты вы обошли и где сейчас находитесь.

    Ребра есть:
    Из вершины ({}, 0) во все вершины ({v},v) ценой goblinTime[v]: это мы можем зайти в лабиринт в любую комнату и должны там гоблина победить.
    Из вершины (S, v) в вершину (S,u) ценой path[v,u], если u в S - это мы идем в ранее посещенную комнату.
    Из вершины (S, v) в вершину (S+{u},u) ценой path[v,u]+goblitTime[u], если u не в S - это мы идем в ранее не посещенную комнату и бъем там гоблина.

    В этом графе на n2^n вершин вам надо найти все кратчайшие пути из начальной ({},0) во все вершины (например, дейкстрой). Потом переберите все вершины в графе (S, v) и, если вершина соответствует комнате с выходом и вы до нее дошли за время не превосходящее время обрушения, то берите сумму количества золота в комнатах в множестве S в качесвте варианта ответа. Из всех них берите максимум.
    Ответ написан
    Комментировать
  • Почему CRC участка кода меняется при перезапусках проги?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Дело в том, что при загрузке программы загрузчик перезаписывает в ней всякие адреса, которые используются при вызовах функций и переходах. Это нужно из-за того, что программа-то может быть загружена по произвольному адресу. А некоторые команды процессора принимают абсолютный адрес. Так же всякие техники защиты вроде ASLR тут все дополнительно портят. У вас там функции библиотеки вызываются, а где они в памяти лежат - вы заранее узнать не можете. Вот и как минимум аргументы call в памяти оказываются разными.

    И защита ваша ничем не поможет, потому что можно пропатчить не только проверку пароля, но и проверку CRC.
    Ответ написан
  • Как свести задачу к минимальному разрезу?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вам нужен 2-дольный граф. Левая доля соответствует строкам, правая - столбцам. Из истока ребора в левую долю (ценой ri), из правой доли - в сток (ценой ci). Ребра между долями ценой aij.

    Любой разрез тут соответствует покрытию всех вершин. Вы должны разрезать ребро между ij или si или jt что чоответствует покрытию клетки, строки иои столбца.
    Ответ написан
    1 комментарий
  • Где ошибка в доказательстве?

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

    Правильное доказательство весьма простое и без индукции. Общее время будет
    Max(sum{i-начальнику}(bi), max{i - подчиненным}(ai))
    .
    Отсюда видно, что если вы какую-то задачу дали подчиненному, то все задачи с меньшим A нет смысла давать начальнику. Ведь второе слагаемое-максимум от этого не изменится, но первое увеличится. Можно "бесплатно" выполнить эти задачи подчиненными. Поэтому в оптимальном ответе вы даете какое-то множетсво минимальных A подчиненым, а остальные начальнику. Иначе можно какие-то задачи перекинуть с начальника на подчиненного и уменьшить первое слагаемое не меняя второе, уменьшив таким образом ответ, т.е. в этом случае решение точно не оптимальное.
    Чтобы все варианты возможных оптимумов перебрать надо отсортировать задачи по возрастанию A. Это код и делает. поддерживается сумма B у всех оставшихся задач, а от текущей берется A - который и будет максимумом для всех задач с меньшим A.
    Ответ написан
    Комментировать
  • Как решать задачу?

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

    Рассмотрим теперь один уровень, который описан 4 числами a,b,c,d и нам надо оставить как можно больше шаров белого цвета (их d). За один ход мы можем приравнять к 0 одно из 4 чисел и вычесть по 1 из отсавшихся ненулвевых. Ясно, что нет смысла занулять d. Т.о. за 3 хода мы можем получть 0,0,0,max(0,d-3). Но, например, если у нас было 2 2 2 3, то занулив a и b мы уменьшениями на 1 зануляем и c. Т.е. для маленьких чисел имеет смысл подумать в каком порядке их занулять. Но мне лень даже думать как именно - ведь их всего 3 числа - можно тупо перебрать все 6 перестанвок и выбрать ту, в которой за наименьшее количество ходов мы их все занулим.
    Ответ написан
    4 комментария
  • Оптимально ли написана программа по слиянию строк и созданию новой строки?

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

    Во-первых, StringBuilder можно указать итоговый размер в конструкторе. Тогда там не будет лишних выделений памяти. Вы же знаете, что там будет сумма двух длин в итоге.
    Во-вторых, основной цикл лучше гнать не до максимальной длины из двух, а до минимальной. Тогда в цикле не надо никаких проверок, что индекс не вышел за границы строки. После цикла надо будет добавить к собираемой строке кусок одной из двух входных строк. Проверьте, какая строка длиннее и добавьте ровно len1-len2 символов с конца. Используйте метод substring(), чтобы получить этот суффикс и сразу передавайте его в append().

    Вторую часть про символы на четных местах тоже можно соптимизировать. Вы знаете длину ответа заранее, инициализируйте StringBuilder с нужной вместимостью.
    На четных местах будет вторая строка. Ну и в конце только какие-то символы через один из второй строки или из первой, в зависимости, какая длинее. Если передавать в функцию не результат работы первой, а 2 строки, то можно сначала append в stringbuilder substring от второй строки, а потом циклом взять нужное количество символов через один из первой или второй строки. Нарисуйте на бумаге несколько случаев, первая строка длиннее второй или наоборот. Длина второй строки четная/нечетная, длина первой четная/нечетная. В каждом из этих случаев будет +-1 где-то в формулах для индексации. Можно это все удачно записать с помощью деления на 2 нацело и остатка от деления на 2.
    Ответ написан
    1 комментарий
  • Как считать числа из текстового файла в массив на с++?

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

    Читайте циклом while, пока чтение не вернет ошибку:
    int x;
    ifstream f("file.txt");
    while (f >> x) {
      v.push_back(x);
    }
    Ответ написан
    5 комментариев
  • Почему не получается записать данные в память?

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

    Еще стоит проверять размер выделенной памяти. shellSize может вернуться больше исходного размера и вы потом в Write будете записывать больше данных, чем у вас в shellCode есть.
    Ответ написан
    Комментировать
  • Почему в Python последовательность append-ов суммируется в O(n), а не в O(n logn)?

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


    Потому что эти распределения разного размера. Первое - совсем маленькое. Второе чуть больше и т.д. Чтобы суммарно было O(n Log n), каждое из них должно быть пропорционально n.

    1+4+10+⋯≤O(n)


    Вот это и есть ответ. Первые слагаемые маленькие. Получается геометрическая прогрессия, которая дает линейную сумму от n.
    Ответ написан
    Комментировать
  • Как корректно распределить сумму внутри элементов массива?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Во-первых, давайте считать в копейках. Умножте все цены на 100 перед началом алгоритма, и поделите на 100 при выводе. Потому что никогда нельзя деньги считать или хранить в вещественных числах. При сериализации и внешних интерфейсах, конечно, придется запятые ставить, но лучше при выводе выводить x/100, "," и x%100. И молиться, что у читателя хватит точности это прочитать, если он, конечно, не заморачивается с подобным трюком.

    Далее алгоритм (на псевдокоде):
    total_price - изначальная цена. goods[i].price - цена товара, goods[i].amount - количество товара, discount - сколько скидки.
    discount_left = discount
    for i in 1..n {
      cur_discount = discount * goods[i].price / total_price # целочисленное деление нацело с округлением вниз.
      goods[i].price -= cur_discount
      discount_left -= cur_discount*goods[i].amount
    }
    for i in 1..n {
      if discount_left == 0: break
      if goods[i].amount <= discount_left {
        goods[i].price -= 1;
        discount_left -= goods[i].amount
      }  else {
       // разбиваем категорию на 2 штуки, в одной discount_left товаров, в другой остальное.
       new_good = Good{.price = goods[i].price-1, .amount = discount_left}
       goods[i].amount -= discount_left
       discount_left = 0
       goods.append(new_good)
       break
      }
    }


    Как это работает: если бы мы могли идеально делить копейки с любой точностью, то каждый товар получил бы скидку price*discount/total_price. Одинаковый процент скидки везде. но у нас-то целые копейки, поэтому если мы эти скидки округлим вниз, то мы сколько-то копеек недоскинем. Но для каждой штуки товара мы потеряли меньше одной копейки, а значит суммарно - меньше общего количества товаров. Значит можно из каких-то товаров вычесть 1 и все сойдется. Вот и вычитаем из первых discount_left товаров. Если категория целиком покрыта - просто уменьшаем у нее цену. Если нет, то разбиваем на 2 куска и у одного цену уменьшаем.

    Тут могут быть проблемы, если скидка очень большая и есть товары очень маленькой стоимости. Скажем, товар стоимостью 5 копеек и кидка в 85% уже между 0 и 1. Округленная вниз она будет 4, но вот если вы из этого товара потом еще и 1 вычтите, то может так получится, что вы снизите цену до 0. Допустимо ли это? Чтобы этого избежать надо товары отсортировать по убыванию цены. Но все равно может не помочь, тогда надо тогда такие товары ценой в 1 копейку исключить из рассмотрения и запустить цикл вычитания 1 опять, если после цикла discount_left не 0.

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

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

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

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

    по двум сторонам и прилежащему углу.


    А вот это не правда, если угол не между двумя равными сторонами. Вот заданы нам 2 длины и угол. Построим такой треугольник: отрезок заданной длины, луч из одной вершины с заданным уголом, окружность заданной длины из второй вершины. Луч и окружность пересекаются в двух точках. Значит, есть 2 разных варианта для третьей вершины, удовлетворяющих условиям. Т.е. есть 2 разных треугольника у которых равны 2 стороны и угол (не между ними).
    Ответ написан
    1 комментарий
  • Почему не работает программа на C++ с решением задачи об "Игре в жизнь"?

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

    Для этого вам понадобится 2 массива map. Один для текущей итерации, и другой для следующей. Или массив должен быть не bool, а int, и там вы должны разными числами помечать живые клетки, которые умрут, живые клетки, пустые клетки и пустые клетки, которые родятся. В первый проход вы считаете соседей и помечаете клетки, а вторым проходом все изменения применяете.

    Кажется, из-за этого у вас там поле никогда не вымирает и программа не останавливается.
    Ответ написан
    1 комментарий
  • Почему объект не передается по ссылке?

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

    Скорее всего у вас внутри конструктора BoxContainer идет присвоение в член nbox. Но у вас не определен оператор присвоения (или конструктор копирования) для NumberBox. Определите его (можно default). Так что с передачей по ссылке все хорошо, но вот то, что вы дальше с этой ссылкой пытаетесь сделать у вас не работает.

    Руководствуйтесь правилом трех-пяти.
    Ответ написан
    2 комментария
  • Как доказать что мы действительно не пропустим такую пару i,j которая дает правильный ответ в методе двух указателей?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В такой реализации это плохо видно, но можно переписать основной цикл так:
    j = Len(B)-1
    for i in range(len(A)):
      while j >= 0 and A[i] + B[j] > c:
        --j;
      if A[i] + B[j] == c:
        found = True
        break


    В этом случае после цикла while поддерживается инвариант, что a[i]+b[j] <= c и это максимальное такое j.
    Ведь, если этот инвариант поддерживался для пердыдущей итерации, то у нас было a[i-1] +b[j] <=c и a[i-1]+b[j+1]>c. Отсюда получается, a[i]+b[j+1] >= a[i-1]+b[j+1] > c. Т.е. если мы уменьшим j в цикле while инвариант останется действовать - это будет самое большое j, т.ч. a[i]+b[j] <= c.

    А этот инвариант гарантирует, что когда в цикле по i переберется значение из ответа, j гарантированно будет указываать на j из ответа. Потому что, если существуют i', j', т.ч. a[i']+b[j'] = c, то можно увеличить j' пока b там не меняется, т.ч. b[j']>b[j'], отсюда получается a[i']+b[j'] <=c и a[i']+b[j+1] > c - а это и есть наш инвариант. Т.е. на итерации i=i' найдется именно j=j'.
    Ответ написан
    3 комментария
  • В чем суть ассиметричного графа?

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

    Не обязательно все вершины должны иметь разную степень. Но их нельзя поменять местами, потому что они связаны с другими вершинам по разному.
    Ответ написан
    2 комментария
  • Почему не работает выражение в интерпретаторе?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Отладчик есть? Или хотя бы отладочный вывод добавьте. Выводите все переменные там, где они меняются. Мне кажется, что вы из строк все пробелы удаляете и у вас segment получается "sqrt(x);". Ведь stringstream будет читать одно слово целиком до пробельного символа, а их там тупо нет. И потом проверка segment == "sqrt" не срабатывает. Но мне лень ваш код запускать, перепроверьте эту гипотезу сами.

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

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

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

    Если же вам надо много раз для многих точек находить ближайшую из заданных, то имеет смысл построить какой-то индекс по опорным точкам. Какое-нибудь R-tree или квадро-дерево.
    Ответ написан
    Комментировать
  • Почему в данном случае не работает обращение к элементам массива по индексу?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Могли бы вы привести тип PMIB_IPNETTABLE? Поищите ее в исходниках, все должно стать понятно.

    Не специалист по паскалю, но если это структура от winAPI, то она сишная, и там идет работа с указателями и никакой длины массива нет (как часть table). А массивы в паскале по другому реализованы - там длина должна рядом хранится. В этой структуре длина тоже есть, но как часть структуры, а не часть массива. Поэтому с точки зрения паскаля у вас там массив длины 1.
    Через указатели все работает, потому что проверок никаких не делается на выход за границу массива.
    Массив бы тоже сработал, но там проверка длины встроенная.
    Ответ написан
    7 комментариев