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

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

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

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

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

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

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

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

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