Problème
Pour chaque taille de plateau k de 1 à n, comptez le nombre de paires non ordonnées de cases distinctes sur un plateau k par k où deux cavaliers ne peuvent pas s'attaquer. Un cavalier se déplace de deux cases dans un axe et d'une case dans l'autre.
. x . x .
x . . . x
. . K . .
x . . . x
. x . x .K indique un cavalier et x ses destinations possibles, lorsque ces cases se trouvent sur le plateau. Intervertir les deux cavaliers ne crée pas un nouveau placement.
Implémentez two_knights(n).
Entrée
n : La plus grande taille de plateau à considérer.
Sortie
Retournez n valeurs dans l'ordre, pour les tailles de plateau de 1 à n.
Contraintes
1 ≤ n ≤ 10 000. Les résultats tiennent dans des entiers signés 64 bits.
Exemples
Entrée :
n = 3
Sortie attendue :
expected = [0, 6, 28]Entrée :
long long n = 3;
Sortie attendue :
std::vector<long long> expected = {0, 6, 28};Entrée :
long n = 3;
Sortie attendue :
long[] expected = new long[] {0, 6, 28};Explication
Un plateau 1 × 1 ne peut pas contenir deux cavaliers. Un plateau 2 × 2 possède six paires et aucune attaque. Un plateau 3 × 3 possède 36 paires, dont huit sont des attaques, ce qui en laisse 28.
Entrée :
n = 1
Sortie attendue :
expected = [0]Entrée :
long long n = 1;
Sortie attendue :
std::vector<long long> expected = {0};Entrée :
long n = 1;
Sortie attendue :
long[] expected = new long[] {0};Explication
Deux cases distinctes sont requises, mais le plateau n'en possède qu'une seule.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Commence par toutes les paires non ordonnées de cases sur chaque échiquier, puis soustrais les paires où les cavaliers s’attaquent.
Indice 2
Seul un petit nombre fixe de placements d’attaque de cavalier tient dans n’importe quel rectangle de 2 by 3 ou 3 by 2.
Indice 3
Les petits échiquiers comme 1 by 1 et 2 by 2 doivent naturellement donner zéro paire attaquante.
Complexité attendue
temps O(n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.