Столкнулся с задачкой, которую легко переформулировать в терминах олимпиадного программирования. Уверен, такое решалось 100000 раз, но я что-то не придумал быстро элегантного решения (теряются навыки ACM) :)

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

Формально так: есть n целых чисел (балансы друзей), сумма этих чисел равна 0. За ход можно взять пару чисел и прибавить произвольное целое число к первому числу этой пары, при этом отняв от второго.

n1, n2 -> n1'=n1+k, n2'=n2-k

Задача — за наименьшее число ходов превратить все числа в 0.

Не смог убедить себя, что жадный алгоритм работает :)

Единственное, что придумал — пролить макспоток минимальной стоимости через граф с истоком, стоком, слоем должников и слоем кредиторов, где каждый должник соединен с каждым кредитором ребром с пропускной способностью бесконечность. При этом функция стоимости будет странная — 1 если по ребру течет какой-то поток и 0 в противном случае. Вообще не уверен, что алгоритм нахождения потока будет работать с такой функцией.

Короче говоря, я уверен, что это какая-то стандартная задача. Кто напомнит как такое решать?

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

Всем привет!

Сегодня столкнулся с задачей, которая по началу показалась простой, а затем, после некоторых размышлений, поставила меня в тупик)

Собственно, требуется найти минимальный по площади эллипс, такой, что все точки из заданного набора окажутся внутри него. При этом мне даже не нужно решать задачу в общем случае — уже известны координаты центра эллипса. Остается, вроде бы, три свободных параметра. Всегда можно что-нибудь попробовать перебрать за куб, но мне не хочется — я уверен, что есть быстрое и точное решение.

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

Кто-нибудь может посоветовать ресурс или описание известного алгоритма? Можно на английском. Большое спасибо.

Собственно, столкнулся на производстве с такой вот задачей. Дан 3-мерный не обязательно выпуклый многогранник (mesh), грани — треугольники. Задача такая: построить один или несколько многогранников вложенных в данный так, чтобы суммарный объем этих многогранников был максимальным и никакая точка внутренних многогранников не была ближе k мм от внешнего. Проще говоря — вырезать полость (полости) максимального объема так, чтобы "стенки" везде были толщины не менее k мм.

Нужно это, естественно, для 3Д печати. Вот здесь показано как это делать, например, для куба: https://www.shapeways.com/tutorials/creating-hollow-objects Наши модели, само собой, более сложные — фигурки людей и пр.

Сейчас решаем проблему приближенно, строим внутри полости из "кубиков" (вокселей). При большом количестве вокселей результат хороший, но в модели получается очень много вершин и граней и принтеру иногда сносит крышу.

Соответственно требования такие:

• максимальный внутренний объем

• толщина стенок

• количество "внутренних" граней должно быть не больше, чем количество граней в исходном меше

• работает быстро и не жрет память, в идеале O(количество вершин)

• естественно, никаких самопересечений, вырожденных граней и прочего

У кого нибудь есть идеи как написать такой алгоритм? Буду рад любым идеям — можно начать с решения в 2мерном случае, например. Заранее спасибо :)

По учёбе возникла такая задачка, есть заданная таблицей функция f(t), строго говоря, равноотстоящий временной ряд. Информации много, десятки миллионов значений. Нужно находить определённым образом "похожие" участки этого временного ряда, причём участки небольшой фиксированной длины L (L порядка 10-40).

Не первый раз сталкиваюсь с проблемой в IDE Eclipse: некорректно работают функции отладки.

Отладчик заходит в функции, несмотря на то, что используешь Step Over (F6), останавливается в рандомных местах до поставленного брейкпоинта. Каких либо закономерностей в этом поведении не замечено. У кого-нибудь были подобные вопросы, есть ли способы научить Eclipse нормально дебажить?

Добавлено:

Забавно, только что случайно обнаружил решение... Дело в том, что я привык создавать новый проект для каждой задачи (точнее копировать заготовку с методом main и вводом). Все классы в них называются одинаково — Solution. Так вот, брейкпоинты из старых задач я не убирал. Видимо Eclipse имеет такой баг — в отлаживаемой программе использовались брейкпоинты из других программ, не имеющих к ней никакого отношения.

Волшебная кнопочка Remove All Breakpoints избавила меня от проблем =)