Как распределить монеты, чтоб себе оставить как можно больше?
Продолжаем серию задач о Падишахе (Задача 1; Задача 2; Задача 3)
Заскучал наш Падишах, пока было межсезонье. Но тут увеличились попытки разворовывать казну.
И дает Падишах наказ Казначею.
Нанимаешь в охрану 33 стражника охранять казну!
Для этого выделяю тебе 240 монет ежемесячно. Из этих монет назначаешь жалование охранникам.
Ты должен разделить всех охранников на отряды (можешь сделать хоть один отряд из всех, хоть 33 отряда по одному, тут тебе полная воля). А затем выплатить все 240 монет отрядам по своему усмотрению.
Внутри каждого отряда монеты должны разделится поровну. Если же поровну не делится, то остаток они возвращают тебе. Собери все остатки - это будет твое жалование.
1) Как казначею распределить отряды, чтоб получать максимально возможную сумму себе?
Какова эта сумма?
Дополнительный вопрос можно у знать в следующей задаче.
Ответы (4)
пусть Казначей разделил всех стражников на k отрядов
обозначим кол-во стражников в i-м отряде как Вᵢ, получаем
B₁ + B₂ + ... + Bₖ = 33
соответственно, i-му отряду стражников Казначей выделил Аᵢ монет
тогда выгода Сᵢ Казначея от i-го отряда будет равна остатку от целочисленного деления Аᵢ // Вᵢ, а именно:
Аᵢ = (nᵢ * Вᵢ + Сᵢ) где nᵢ - кол-во монет, полученных каждым стражником в в i-м отряде
при этом, по свойству остатков: Вᵢ > Сᵢ
значит Сᵢ ⩽ Вᵢ - 1
теперь попробуем просуммировать все Сᵢ
C₁ + C₂ + ... + Cₖ ⩽ Σ(Вᵢ - 1) = 33 - k
таким образом мы получили оценку сверху для суммарной выгоды Казначея:
ΣСᵢ ⩽ 33 - k
попробуем k = 1
240 // 33 = 7 (здесь // обозначает целочисленное деление - как в Питоне)
выгода Казначея: 240 - 33 * 7 = 9 (как-то маловато...)
попробуем k = 2
разобьем всех стражников на 2 группы, а именно:
- первая группа - 32 стражника и выдадим им например: 32 + 31 = 63 монеты
- вторая группа - 1 стражник, он получит все оставшиеся монеты
Итого: выгода Казначея при данном раскладе составит 31 монету - т.е максимально допустимую выгоду для k = 2
для остальных вариантов ( k ≥ 3), получаем ΣСᵢ ⩽ 33 - 3 = 30
Ответ: максимальная выгода Казначея: 31 монета
Как не крути,по сколько не давай стражникам, все равно речь идет о сумме остатков.
Вот и разделим стражников на 2 отряда, например:
(15 +18) или (16+17) или (19+14)
Будут остатки:
14+17=15+16=31
То есть казначей может возможно получить 31 монету.Но так ли это?
Как, например?.Подберем.
Пусть у нас 29+3+1=33
На первых 29 стражников выделяется 203 монеты
203=6*29+(28 остаток)
Осталось 240-203=37 монет
Трем стражникам выделяем 35 монет. Казначей получает 2 монеты.
В общем я с цифрами поэкспериментировал и получается, что Казначей может получить, как Иуда 30 сребренников.
Но и 31 может тоже получить.
Это вариант 32+1=33
240-33=217
217=32*6+31(ост)
Казначей получает остаток 31 монету.
Последний стражник получает все оставшиеся 33 монеты.
Или я неправильно понял вопрос, или ответ элементарный:
Делаем 33 отряда по 1 человеку, каждому платим по 1 монете, остальное забираем себе.
Получается 240 - 33 = 207 монет.
Наши начальники в основном так и платят работягам.
Например, группе из 7 человек нужно дать 13 монет. Тогда каждому достанется по 1 монете, и 6 в остатке уйдет казначею.
Я не совсем понял условие этой задачи.
Даю такое решение.
Можно стражников разделить на три отряда по 5, 7 и 11 стражников в каждом отряде.
Тогда отрядам достаётся ровно по 80 монет.
В первом отряде стражники получат по 16 монет, во втором отряде стражники получат по 11 монет, в третьем отряде стражники получат по 7 монет. Казначей получит остатки от деления в виде 13 монет.
80 на 5 делятся без остатка по 16 и с 1-го отряда казначей не получит ничего, а со 2-го и 3-го по 3 монеты. Итого 6 монет. Вы считаете, что это максимум?
Цель в задаче получить максимум. Постарайтесь доказать, что больше нельзя тогда.
Спойлер: 6 - это мало.
ВКонтакте