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.

No comments:

If you have any doubt or suggestion let me know in comment section.

Powered by Blogger.