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

Question

[Homemade]

Задача

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

https://codeforces.com/problemset/problem/1476/A

Разбор задачи

здесь

https://codeforces.com/blog/entry/87356

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

Как ⌈n/k⌉ превратилось в ⌊(n+k−1)/k⌋ ?

Comments

[Василий Банников]

При целочисленном делении отбрасывается дробная часть

[Homemade]

Василий Банников, Это я знаю

[Евгений Шатунов]

Homemade, а к чему в вопросе тег C++?

[Homemade]

Евгений Шатунов, я подумал, может пригодиться для пишущего ответ.

[Евгений Шатунов]

Homemade, нет, не пригодится. Пригодится только если у тебя вопрос в сторону стандарта языка.

Answer 1

[Lynn «Кофеман»]

Пусть 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

Comments

[Homemade]

Благодарю!

Answer 2

[galaxy]

Если n не делится на k, то ⌈n/k⌉ = ⌊n/k + 1⌋ = ⌊(n+k)/k⌋
Единица отнимается, чтобы захватить случай n, делящегося на k (при k > 1 на первый случай это не повлияет)

Comments

[Homemade]

Спасибо за помощь!

Answer 3

[Wataru]

(n+k-1) / k даст округление вверх, потому что прибавление k-1 к числителю переваливает его за следующее делящееся на k число после n. Если остаток от деления n на k был не ноль, то мы к этому остатку прибавили k-1 и получили число не меньше k, которое даст +1 к результату деления (что тут и нужно, ведь при неделящемся на k n - округление вверх на 1 больше округления вниз). Если же n делилось на k, то прибавление k-1 не перевалит за следующее делящееся на k число и результат деления не поменяется.

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

Comments

[Homemade]

Спасибо вам большое!