Problème
La case 1 contient un grain. Chaque case suivante contient deux fois plus de grains que la case précédente. Retournez à la fois le nombre de grains sur la case demandée et le total sur les cases 1 à 64. Écrivez chaque nombre sous forme de texte décimal, car le total de l'échiquier dépasse la capacité d'un entier signé 64 bits.
Implémentez chessboard_grains(square).
Entrée
square : La case demandée, numérotée à partir de 1.
Sortie
Retournez deux chaînes décimales : [nombre de grains sur la case demandée, total sur les 64 cases].
Contraintes
1 ≤ square ≤ 64. Les chaînes de sortie ne contiennent que des chiffres décimaux, sans virgules, espaces ni zéros initiaux.
Exemples
Entrée :
square = 6
Sortie attendue :
expected = ["32", "18446744073709551615"]Entrée :
long long square = 6;
Sortie attendue :
std::vector<std::string> expected = {"32", "18446744073709551615"};Entrée :
long square = 6;
Sortie attendue :
string[] expected = new string[] {"32", "18446744073709551615"};Explication
Les six premiers nombres sont 1, 2, 4, 8, 16, 32. Le total de l'échiquier est 1 + 2 + … + 2⁶³ = 2⁶⁴ − 1.
Entrée :
square = 1
Sortie attendue :
expected = ["1", "18446744073709551615"]Entrée :
long long square = 1;
Sortie attendue :
std::vector<std::string> expected = {"1", "18446744073709551615"};Entrée :
long square = 1;
Sortie attendue :
string[] expected = new string[] {"1", "18446744073709551615"};Explication
La première case contient 1 grain. Le second résultat fait toujours référence à l'ensemble des 64 cases, et non à un simple préfixe.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Chaque case double la précédente, donc la quantité demandée dépend seulement de sa position.
Indice 2
Le total sur les 64 cases suit une progression géométrique, et il dépasse très vite les limites des entiers usuels.
Indice 3
Renvoie les deux valeurs en texte décimal brut, et rappelle-toi que la première case vaut un, pas zéro.
Complexité attendue
temps O(1), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.