Да, фигли тут парится
Перенумеруем последовательно мешки от 0 до N – 1. Обозначим вес самой лёгкой монеты через m. Пусть мешок под номером j содержит монеты веса m + Δj, то есть Δj определяет сорт монеты в j-м мешке. Пусть в зависимости от сорта монеты величины Δ могут принимать (целые) значения 0, 1, 2, ..., меньшие k, то есть количество сортов монет равно k.
Теперь возьмем из мешка с номером j количество монет, равное k j, то есть из первого мешка – одну монету, из второго – k, ..., из последнего – kN–1 монет. Всего взятых монет будет N–1
M = ∑ k j = 1 + k + k2 + ... + kN–1 = kN – 1
k – 1
.
j=0
Их суммарный вес S на весах будет равен N–1 N–1
S = ∑ (m + Δj )k j = m·M + ∑ Δj k j.
j=0 j=0
Поскольку всегда Δj < k, вторая сумма в правой части N–1
Δ = ∑ Δj k j = Δ0 + Δ1 k + Δ2 k2 + ... + ΔN–1kN–1
j=0
представляет собой перевод числа Δ из десятичной системы счисления (в которой работают весы) в систему счисления с основанием, равным k. В этой системе Δ записывается в виде числа со следующей последовательностью цифр:
Δ → ΔN–1 ΔN–2 ... Δ2 Δ1 Δ0 .
(*)
Мы видим, что каждая цифра этой записи показывает сорт монеты в последовательности мешков, взятой в обратном порядке. В этом состоит суть нашего решения.
Итак, из суммарного веса S всех выбранных M монет вычитаем величину Mm – вес того же количества монет наилегчайшего сорта и оставшееся число Δ = S – Mm переводим в систему счисления с основанием k (разлагаем по степеням k, начиная со старшей). Тогда мы получим число вида (*). Его j-я цифра с конца (счёт ведётся от нуля) показывает сорт монеты Δj в мешке под номером j.
yaplakal.com