H
H
Homemade2021-01-31 14:12:03
Algorithms
Homemade, 2021-01-31 14:12:03

Rounding during integer division, how to understand?

Task

1476A - Sum multiple of K
https://codeforces.com/problemset/problem/1476/A

Problem analysis
here
https://codeforces.com/blog/entry/87356

Incomprehensible moment:
It is quite obvious that the smaller s, the smaller the maximum ai, that is, we need to find the minimum cf such that cf⋅k≥n. Then cf=⌈n/k⌉=⌊(n+k−1)/k⌋.

How did ⌈n/k⌉ become ⌊(n+k−1)/k⌋ ?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
L
Lynn "Coffee Man", 2021-01-31
@Homemade

Let n = pk + d, where 1 <= d <= p
Then ⌈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, because 0 <= d - 1 < k

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question