Problème
Trouvez des entiers positifs a < b < c tels que a² + b² = c² et a + b + c = perimeter. Retournez le plus grand produit a × b × c parmi les triangles admissibles, ou −1 s’il n’en existe aucun. Ceci généralise le problème source à périmètre fixé et gère explicitement les cas à plusieurs réponses.
Implémentez pythagorean_product(perimeter).
Entrée
perimeter : La somme requise des trois côtés.
Sortie
Retournez le plus grand produit, ou −1 si aucun triangle ne convient.
Contraintes
3 ≤ perimeter ≤ 100 000. Les produits tiennent dans un entier signé 64 bits.
Exemples
Entrée :
perimeter = 30
Sortie attendue :
expected = 780Entrée :
long long perimeter = 30;
Sortie attendue :
long long expected = 780;Entrée :
long perimeter = 30;
Sortie attendue :
long expected = 780;Explication
Le triangle est (5, 12, 13) : 25 + 144 = 169 et 5 + 12 + 13 = 30. Son produit est 780.
Entrée :
perimeter = 11
Sortie attendue :
expected = -1Entrée :
long long perimeter = 11;
Sortie attendue :
long long expected = -1;Entrée :
long perimeter = 11;
Sortie attendue :
long expected = -1;Explication
Aucun triplet croissant d’entiers positifs formant un triangle rectangle n’a pour somme 11.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Seules certaines valeurs de périmètre peuvent former un triangle rectangle, donc commence par réduire la recherche avec la contrainte sur la somme des côtés.
Indice 2
Pour chaque plus petit côté possible, déduis les deux autres à partir du périmètre et vérifie la condition du triangle rectangle.
Indice 3
Plus d’un triangle peut convenir ; garde le plus grand produit et renvoie aucune solution si rien n’est valide.
Complexité attendue
temps O(perimeter^2), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.