It all about maths I don't understand, how can I solve this exercise, someone say that is a 2-dimensional problem, but I can not figure out for myself, I already understand what to do, but I don't know why is the formula, can someone explain this exercise for a dummy? http://www.codeforces.com/contest/1/problem/A
Why the solution of this problem is (m+a−1a×n+a−1a)?
Help really appreciated.
Answer
So break it into one dimensional problems. How many flagstones of length a does it take to cover a path of m meters? If you can trust a and m to be integers, m/a is correct if a divides m. Otherwise you need ⌊m/a⌋+1. One way to combine these is ⌊(m+a−1)/a⌋. Try it with some small numbers to see how it works.
For two dimensions, just multiply two one dimensional problems.
No comments:
Post a Comment