0
$\begingroup$

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.

  • 0
    People here are generally not inclined to write you complete solutions, but they will usually answer specific questions. If you can explain clearly what you understand and precisely what you do not understand, using complete sentences and correct grammar, that will be helpful.2010-12-06
  • 0
    -1. Please ask complete questions instead of linking to external sources.2010-12-06
  • 0
    @Nate Eldredge,@ Akhil Mathew I already edit2010-12-06

2 Answers 2

2

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.

  • 0
    ok I am understanding, thanks for answering, this problems are too mathematical that sometimes I try but when I read the tutorial I say WHAT?? where do they get that formula?2010-12-07
0

The answer is (the area to cover) / (the area per flagstone) + (penalty for having to use whole flagstones). Note that your answer is almost equal to (m*n)/(a*a) so it looks about right.

  • 0
    but I still dont know how to get to that formula, I see that formula in a tutorial, thanks for answer2010-12-06
  • 0
    i guess you need to study more algebraic geometry2010-12-06
  • 0
    I think so, I need to learn more some similar example??2010-12-06
  • 0
    which formula do you not understand? your original formula? my formula with words? my simplified formula with letters? all of them?2010-12-06
  • 0
    I dont understand how to obtain the original formula, ((m+a-1)/a)*((n+a-1)/a), how can I figure out that formula?, of course I understand your formulas2010-12-06
  • 0
    You are right, the formula you were given is not correct. If a=m=n=2 then you get 9/4 which is not an integer number of flagstones.2010-12-07
  • 0
    @minel: As this is a computer science problem and the numbers are integers, you need to use integer division. Adding the a-1 into the numerator takes care of fractional tiles.2010-12-07
  • 0
    @Ross Millikan , do you have some similar example of this computer problem?, in maths of course2010-12-07
  • 0
    @GeorgeBecj: I'm not sure what you mean by similar problems. One class would be to use some other tiling of the plane. Say your tiles are regular hexagons. For simplicity, specify that one corner goes on the corner of the plaza and one side goes along the side of the plaza. Now how many tiles do you need? For equilateral triangles? The octagon/square tiling? You have to think about the geometry to find the formulas.2010-12-07
  • 0
    ok I was thinking is just what you said, thanks for all2010-12-07