Problem
Für jede Brettgröße k von 1 bis n sollst du die ungeordneten Paare verschiedener Felder auf einem k×k-Brett zählen, auf denen zwei Springer einander nicht angreifen können. Ein Springer zieht zwei Felder in einer Richtung und eines in der anderen.
. x . x .
x . . . x
. . K . .
x . . . x
. x . x .K markiert einen Springer und x dessen mögliche Zielfelder, sofern diese auf dem Brett liegen. Das Vertauschen der beiden Springer ergibt keine neue Platzierung.
Implementiere two_knights(n).
Eingabe
n: Die größte zu betrachtende Brettgröße.
Ausgabe
Gib n Zahlen in Reihenfolge zurück, für die Brettgrößen 1 bis n.
Einschränkungen
1 ≤ n ≤ 10.000. Die Anzahlen passen in vorzeichenbehaftete 64-Bit-Ganzzahlen.
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
Ein 1×1-Brett kann keine zwei Springer aufnehmen. Ein 2×2-Brett hat sechs Paare und keine Angriffe. Ein 3×3-Brett hat 36 Paare, von denen acht angreifen, sodass 28 übrig bleiben.
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
Es werden zwei verschiedene Felder benötigt, aber das Brett hat nur eines.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Beginne mit allen ungeordneten Paaren von Feldern auf jedem Brett und ziehe dann die Paare ab, bei denen sich die Springer angreifen.
Hinweis 2
Nur eine kleine, feste Anzahl von Springer-Angriffspositionen passt in jedes 2 by 3- oder 3 by 2-Rechteck.
Hinweis 3
Randfälle wie 1 by 1 und 2 by 2 müssen natürlich null angreifende Paare ergeben.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.