Getting started with Codeforces: Part 4: Solving your first problem (Theatre Square) in codeforces.

First of all you have to understand the problem completely. I suggest to read part 3 for that.

Let's solve a mini problem first. We consider a line instead of a matrix.

To cover a line m, with length of 6 by stick a with length of 4, we need at least 2 sticks. See image below:

Let's have another example:  m=13, a=3

we see that at least 5 stick requires to cover the line fully. if the line length were 12, only 4 stick would be enough. 

Now we can understand and calculate visually, can we calculate required number of stick mathematically? 

yes, we can. For m=13 and a=3, required stick is simply  m/a >> 13/3 >> 4.33

Wait a minutes, we can not take 0.33 stick as we are not allowed to break it. In this case, 5 stick is needed. 

For m=12 and a=3, required stick is m/a=12/3=4.0, as no partial part needed, the answer is 4. 

Simplest way to handle this with Integer data type is: 

If the line length is divisible by stick length the answer is m/a, 

If there is some reminder the answer is m/a+1. 

In C++, 

Answer  = m /a;

 If(m%a != 0) Answer++;

Simple, right?

Now, tell me how many cell in the following matrix?

36? how did you calculate that? You have calculated the number of row (6) and column (6) and multiplied them (6*6=36) instead of counting all the cell one by one, right? 

We can apply this trick solving the main problem. We will count how many square require to cover vertically and how many horizontally and then multiply them to get the answer. 

For m=6, n=6, a=4. 

Vertically requires m/a = 6/4 = 1.5 = 2 (round up) 

Horizontally requires n/a = 6/4 =1.5 = 2 (round up) 

So, total minimum required square is 2*2 = 4. 

That's it...... 

Nope, That's not all actually, you will get "Wrong Answer" verdict. Look at the constraints. 

what if the input is m=10^9, n=10^9 and a=1? Answer will be 10^18 which is out of Integer range, in that case, you need to use "long long" data type instead of "integer". 

Next: Solving your second problem in codeforces