Problema
Para cada tamaño de tablero k desde 1 hasta n, cuenta los pares no ordenados de casillas distintas en un tablero de k por k donde dos caballos no puedan atacarse entre sí. Un caballo se mueve dos casillas en un eje y una en el otro.
. x . x .
x . . . x
. . K . .
x . . . x
. x . x .K marca un caballo y x sus posibles destinos, cuando esas casillas están dentro del tablero. Intercambiar los dos caballos no genera una colocación diferente.
Implementa two_knights(n).
Entrada
n: El mayor tamaño de tablero a considerar.
Salida
Devuelve n conteos en orden, para los tamaños de tablero desde 1 hasta n.
Restricciones
1 ≤ n ≤ 10,000. Los conteos caben en enteros con signo de 64 bits.
Ejemplos
Entrada:
n = 3
Salida esperada:
expected = [0, 6, 28]Entrada:
long long n = 3;
Salida esperada:
std::vector<long long> expected = {0, 6, 28};Entrada:
long n = 3;
Salida esperada:
long[] expected = new long[] {0, 6, 28};Explicación
Un tablero de 1 × 1 no puede contener dos caballos. Un tablero de 2 × 2 tiene seis pares y ningún ataque. Un tablero de 3 × 3 tiene 36 pares, de los cuales ocho se atacan, quedando 28.
Entrada:
n = 1
Salida esperada:
expected = [0]Entrada:
long long n = 1;
Salida esperada:
std::vector<long long> expected = {0};Entrada:
long n = 1;
Salida esperada:
long[] expected = new long[] {0};Explicación
Se requieren dos casillas distintas, pero el tablero solo tiene una.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Empieza con todos los pares no ordenados de casillas en cada tablero y luego resta los pares donde los caballos se atacan.
Pista 2
Solo caben un número pequeño y fijo de colocaciones de ataque en cualquier rectángulo de 2 por 3 o 3 por 2.
Pista 3
Los tableros extremos como 1 por 1 y 2 por 2 deben dar naturalmente cero pares atacantes.
Complejidad esperada
tiempo O(n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.