Problema
Per ogni dimensione di scacchiera k da 1 a n, conta le coppie non ordinate di caselle distinte su una scacchiera k per k in cui due cavalieri non possono attaccarsi a vicenda. Un cavaliere si muove di due caselle in un asse e di una nell'altro.
. x . x .
x . . . x
. . K . .
x . . . x
. x . x .K indica un cavaliere e x le sue possibili destinazioni, quando quelle caselle si trovano sulla scacchiera. Scambiare i due cavalieri non genera una nuova disposizione.
Implementa two_knights(n).
Input
n: La dimensione massima della scacchiera da considerare.
Output
Restituisci n conteggi in ordine, per le dimensioni della scacchiera da 1 a n.
Vincoli
1 ≤ n ≤ 10.000. I conteggi rientrano nei numeri interi con segno a 64 bit.
Esempi
Input:
n = 3
Output atteso:
expected = [0, 6, 28]Input:
long long n = 3;
Output atteso:
std::vector<long long> expected = {0, 6, 28};Input:
long n = 3;
Output atteso:
long[] expected = new long[] {0, 6, 28};Spiegazione
Una scacchiera 1 × 1 non può contenere due cavalieri. Una scacchiera 2 × 2 ha sei coppie e nessun attacco. Una scacchiera 3 × 3 ha 36 coppie, di cui otto si attaccano, lasciandone 28.
Input:
n = 1
Output atteso:
expected = [0]Input:
long long n = 1;
Output atteso:
std::vector<long long> expected = {0};Input:
long n = 1;
Output atteso:
long[] expected = new long[] {0};Spiegazione
Sono richieste due caselle distinte, ma la scacchiera ne ha solo una.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Inizia con tutte le coppie non ordinate di caselle su ogni scacchiera, poi sottrai le coppie in cui i cavalli si attaccano.
Suggerimento 2
Solo un piccolo numero fisso di disposizioni di attacco del cavallo entra in un rettangolo 2 by 3 o 3 by 2.
Suggerimento 3
Scacchiere di bordo come 1 by 1 e 2 by 2 devono produrre naturalmente zero coppie in attacco.
Complessità attesa
tempo O(n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.