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×N grid where (i,j) denotes the intersection of the i-th row and the j-th column, a pook placed at square (x,y) threatens the following squares:

  • (i,y) for every 1iN
  • (x,i) for every 1iN
  • (x+1,y1), if x<N and y2
  • (x+1,y+1), if x<N and y<N

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

Input Format

  • The first line of input will contain a single integer T, 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 N.

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.

Constraints

  • 1T105
  • 1N109

Sample Input 1

3
1
2
3

Sample Output 1

1
1
2

Explanation

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

Test case 2: 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 3: Placing 2 pooks on a 3×3 grid is easy — for example, place one at (1,2) and another at (3,3). It can be shown that placing three is not possible.

Leave a Comment