Đề bài
For each board size k from 1 through n, count unordered pairs of distinct squares on a k by k board where two knights cannot attack each other. A knight moves two squares in one axis and one in the other.
. x . x .
x . . . x
. . K . .
x . . . x
. x . x .K marks a knight and x its possible destinations, when those squares lie on the board. Swapping the two knights does not create another placement.
Implement two_knights(n).
Input
n: The largest board size to consider.
Output
Return n counts in order, for board sizes 1 through n.
Ràng buộc
1 ≤ n ≤ 10,000. Counts fit signed 64-bit integers.
Ví dụ
Đầu vào:
n = 3
Kết quả mong đợi:
expected = [0, 6, 28]Đầu vào:
long long n = 3;
Kết quả mong đợi:
std::vector<long long> expected = {0, 6, 28};Đầu vào:
long n = 3;
Kết quả mong đợi:
long[] expected = new long[] {0, 6, 28};Giải thích
A 1 × 1 board cannot hold two knights. A 2 × 2 board has six pairs and no attacks. A 3 × 3 board has 36 pairs, of which eight attack, leaving 28.
Đầu vào:
n = 1
Kết quả mong đợi:
expected = [0]Đầu vào:
long long n = 1;
Kết quả mong đợi:
std::vector<long long> expected = {0};Đầu vào:
long n = 1;
Kết quả mong đợi:
long[] expected = new long[] {0};Giải thích
Two distinct squares are required, but the board has only one.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Start with all unordered pairs of squares on each board, then subtract the pairs where knights attack.
Gợi ý 2
Only a small, fixed number of knight attack placements fit inside any 2 by 3 or 3 by 2 rectangle.
Gợi ý 3
Edge boards like 1 by 1 and 2 by 2 need to naturally produce zero attacking pairs.
Độ phức tạp mong đợi
O(n) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.