@Homemade

Округление при целочисленном делении, как понять?

Задача
1476A - Сумма, кратная K

Разбор задачи
Непонятный момент :
Довольно очевидно, что чем меньше s — тем меньше максимальное ai, то есть нам надо найти миниальное cf такое, что cf⋅k≥n. Тогда cf=⌈n/k⌉=⌊(n+k−1)/k⌋.

Как ⌈n/k⌉ превратилось в ⌊(n+k−1)/k⌋ ?
  • Вопрос задан
  • 71 просмотр
Решения вопроса 3
Lynn
@Lynn
nginx, js, css
Пусть n = pk + d, где 1 <= d <= p
Тогда ⌈n/k⌉ = p + 1
n + k - 1 = pk + d + k - 1 = (p + 1)k + (d - 1)
⌊(n+k−1)/k⌋ = ⌊p + 1 + (d - 1)/k⌋ = p + 1, т.к. 0 <= d - 1 < k
Ответ написан
@galaxy
Если n не делится на k, то ⌈n/k⌉ = ⌊n/k + 1⌋ = ⌊(n+k)/k⌋
Единица отнимается, чтобы захватить случай n, делящегося на k (при k > 1 на первый случай это не повлияет)
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
(n+k-1) / k даст округление вверх, потому что прибавление k-1 к числителю переваливает его за следующее делящееся на k число после n. Если остаток от деления n на k был не ноль, то мы к этому остатку прибавили k-1 и получили число не меньше k, которое даст +1 к результату деления (что тут и нужно, ведь при неделящемся на k n - округление вверх на 1 больше округления вниз). Если же n делилось на k, то прибавление k-1 не перевалит за следующее делящееся на k число и результат деления не поменяется.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы