Codeforces #662, Div - 2 A

 Question

You are given n * n grid & you have to color it forming chess like pattern. Two players are playing this game. Basically we can say that the blocks placed by player must touch the boundary & must be alternate.

 

Suppose you are given grid of 1 * 1 then only 1 chance will take to color. For 2 * 2 we can do this in 2 turns.

 

Now for 3 * 3

        

As you can see first we filled the blocks touching the sides in alternate manner & then the rest.

 

Now for 4 * 4

 

We will follow same process; first we will fill the blocks in alternate manner touching the boundary. Second turn we can now suppose previously filled cells as boundary & fill with blocks in alternate manner. Hence this all will take 3 steps to complete.

 

 

 

Similarly we will do for 5 * 5 which will also take 3 steps to complete.

 

 

 

Now coming to approach :

 

You can see a pattern is forming. The turns required to fill the block goes 1 for 1 * 1 then 2 for 2 * 2 then 2 for 3 * 3 then 3 for 4 * 4 then 3 for 5 * 5 and so on... So here is the pattern 1 1 2 2 3 3 4 4 5 5...

 

Simply we have to print n / 2 + 1 & that is the answer.

Solution