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 $(\dfrac{m+a-1}{a}\times \dfrac{n+a-1}{a})$?
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 $\lfloor{m/a}\rfloor+1$. One way to combine these is $\lfloor(m+a-1)/a\rfloor$. 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