August 22nd, 2014

nyaload

В один мешок помещается K яблок. Сколько мешков надо, если яблок - N штук.

Часто встречающаяся в программировании (тривиальная) задача:
В один мешок помещается K яблок. Сколько мешков надо, если яблок - N штук.
Нет, не N/K. И даже не (N/K)+1. На самом деле, (N+K-1)/K.

Убираем одно яблоко (т.е. остаётся N-1), если какой-то мешок заполнен не полностью, то убираем именно из него. Смотрим сколько полностью заполненных мешков нужно для такого количества. Это (N-1)/K. Добавляем обратно тот мешок, из которого вынули яблоко, получаем на 1 больше, т.е. 1 + (N-1)/K.
Почему именно одно яблоко? Потому что похожее рассуждение "уберем 0 яблок" не работает для N=42*K, а "уберём 2 яблока" не работает для N=42*K+1. Требуется чтобы мешок из которого убрали яблоки - был ровно один (для двух яблок это не так), и чтобы он перестал быть полным (для 0 яблок это не так).

Можно ещё рассуждать так: количество мешков увеличивается монотонно, и ровно на 1 при увеличении N на K. Отсюда визуальный способ мышления подсказывает, что график формулы - это "лесенка", где длина ступеньки равна K. Такая лесенка задаётся формулой N/K. Осталось только понять, как сместить вверх и вбок такой график для совпадения с искомой формулой. Значит формула должна быть вида константа1 + (N+константа2)/K, осталось подобрать константы. Разрыв в количестве мешков - в тот момент, когда яблок на одно больше, чем для полного заполнения всех мешков (т.е. N делится на K). Отсюда константа2=-1. константа1 подбирается на любом частном случае.

Чтобы формула корректно работала для N=0 и не делить отрицательное (N-1) - надо переместить слагаемое-единицу в знаменатель дроби, т.е. формула становится (N+K-1)/K.
В C/C++ отрицательные числа делятся не так, как в Python, в Python деление -1 на K сработает корректно и можно использовать 1+(N-1)/K, в C/C++ - нет, и лучше использовать (N+K-1)/K
Если K - степень двойки, то такой проблемы нет, битовые знаковые сдвиги отработают корректно в 1+((N-1)>>10).
Если N настолько большое, что есть риск IntegerOverflow - то N/K + bool(N%K)

Вроде тривиально, но как часто люди до этого не додумываются и лепят или каких-то монстров, или double-арифметику, или тратят один лишний мешок.