Problema
Para cada tamanho de tabuleiro k de 1 até n, conte os pares não ordenados de casas distintas em um tabuleiro k por k onde dois cavalos não podem se atacar. Um cavalo se move duas casas em um eixo e uma no outro.
. x . x .
x . . . x
. . K . .
x . . . x
. x . x .K marca um cavalo e x seus possíveis destinos, quando essas casas estão dentro do tabuleiro. Trocar os dois cavalos não cria um novo posicionamento.
Implemente two_knights(n).
Entrada
n: O maior tamanho de tabuleiro a considerar.
Saída
Retorne n contagens em ordem, para os tamanhos de tabuleiro de 1 até n.
Restrições
1 ≤ n ≤ 10.000. As contagens cabem em inteiros assinados de 64 bits.
Exemplos
Entrada:
n = 3
Saída esperada:
expected = [0, 6, 28]Entrada:
long long n = 3;
Saída esperada:
std::vector<long long> expected = {0, 6, 28};Entrada:
long n = 3;
Saída esperada:
long[] expected = new long[] {0, 6, 28};Explicação
Um tabuleiro 1 × 1 não comporta dois cavalos. Um tabuleiro 2 × 2 tem seis pares e nenhum ataque. Um tabuleiro 3 × 3 tem 36 pares, dos quais oito se atacam, restando 28.
Entrada:
n = 1
Saída esperada:
expected = [0]Entrada:
long long n = 1;
Saída esperada:
std::vector<long long> expected = {0};Entrada:
long n = 1;
Saída esperada:
long[] expected = new long[] {0};Explicação
São necessárias duas casas distintas, mas o tabuleiro tem apenas uma.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Comece com todos os pares não ordenados de casas em cada tabuleiro e depois subtraia os pares em que os cavalos se atacam.
Dica 2
Só um número pequeno e fixo de posições de ataque do cavalo cabe em qualquer retângulo 2 por 3 ou 3 por 2.
Dica 3
Tabuleiros extremos como 1 por 1 e 2 por 2 devem naturalmente resultar em zero pares de ataque.
Complexidade esperada
tempo O(n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.