PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Lavish Gupta
Testers: Satyam, Abhinav Sharma
Editorialist: Nishank Suresh
DIFFICULTY:
To be calculated
PREREQUISITES:
None
PROBLEM:
A queen is placed at cell (X, Y) on a N\times N chessboard. How many cells does it attack?
EXPLANATION:
Let’s separately count the squares that are under attack horizontally, vertically, and diagonally. Our answer is the sum of these squares.
- Horizontally: The queen can move any number of squares horizontally. So, every square in its row is under attack, apart from the one it’s standing on. This gives us N-1 squares.
- Vertically: The exact same reasoning as the horizontal case gives us N-1 more squares in this case as well.
-
Diagonally: There are two diagonals to consider, so once again we count them separately and add up.
- One diagonal consists of all squares (A, B) such that A+B = X+Y. A little experimenting on paper should show you that the number of squares on this diagonal is the difference between N+1 and X+Y, i.e, |(N+1) - (X+Y)|. Subtract one from this to account for the square the queen is standing on.
- The other diagonal consists of all squares (A, B) such that A - B = X - Y. Once again, a little experimenting will show that the number of squares on this diagonal is N - |X - Y|, from which we subtract one.
Add up the answers to these four cases to obtain the final answer.
TIME COMPLEXITY:
\mathcal{O}(1) per test.
CODE:
Python
for _ in range(int(input())):
n, x, y = map(int, input().split())
ans = 2*n # row + column
ans += n - abs(x - y) # diagonal 1
ans += n - abs(n+1 - (x + y)) # diagonal 2
print(ans - 4)