[Solution] Game of Pooks solution codechef

Game of Pooks solution codechef – We have found a new chess character — pook. It has the qualities of both a rook and a pawn. Specifically, treating the chessboard to be an N×NN×N grid where (i,j)(i,j) denotes the intersection of the ii-th row and the jj-th column, a pook placed at square (x,y)(x,y) threatens the following squares:

[Solution] Game of Pooks solution codechef

  • (i,y)(i,y) for every 1iN1≤i≤N
  • (x,i)(x,i) for every 1iN1≤i≤N
  • (x+1,y1)(x+1,y−1), if x<Nx<N and y2y≥2
  • (x+1,y+1)(x+1,y+1), if x<Nx<N and y<Ny<N

Find the maximum number of pooks that can be placed on an empty N×NN×N chessboard such that none of them threaten each other.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases. Then the test cases follow.
  • Each test case consists of a single line of input, containing a single integer NN.

Output Format

For each test case, output in a single line the maximum number of pooks that can be placed on the chessboard such that they don’t threaten each other.

[Solution] Game of Pooks solution codechef

  • 1T1051≤T≤105
  • 1N1091≤N≤109

Sample Input 1 

3
1
2
3

Sample Output 1 

1
1
2

Game of Pooks solution Explanation

Test case 11: There is a single square, so we have a single pook.

Test case 22: We can only place one pook. No matter where the first is placed, placing a second will lead to one of the two being threatened.

Test case 33: Placing 22 pooks on a 3×33×3 grid is easy — for example, place one at (1,2)(1,2) and another at (3,3)(3,3). It can be shown that placing three is not possible.

For Solution

Click here

Leave a Comment