Problem
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.
Einschränkungen
1 ≤ n ≤ 10,000. Counts fit signed 64-bit integers.
Beispiele
Eingabe:
n = 3
Erwartete Ausgabe:
expected = [0, 6, 28]Eingabe:
long long n = 3;
Erwartete Ausgabe:
std::vector<long long> expected = {0, 6, 28};Eingabe:
long n = 3;
Erwartete Ausgabe:
long[] expected = new long[] {0, 6, 28};Erläuterung
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.
Eingabe:
n = 1
Erwartete Ausgabe:
expected = [0]Eingabe:
long long n = 1;
Erwartete Ausgabe:
std::vector<long long> expected = {0};Eingabe:
long n = 1;
Erwartete Ausgabe:
long[] expected = new long[] {0};Erläuterung
Two distinct squares are required, but the board has only one.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Start with all unordered pairs of squares on each board, then subtract the pairs where knights attack.
Hinweis 2
Only a small, fixed number of knight attack placements fit inside any 2 by 3 or 3 by 2 rectangle.
Hinweis 3
Edge boards like 1 by 1 and 2 by 2 need to naturally produce zero attacking pairs.
Erwartete Komplexität
O(n) time, O(1) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.