Two-sum (python)

Énoncé

Soit la liste (déjà triée croissante) de 10 entiers distincts :

7 69 81 85 109 138 140 158 187 197

Trouvez i < j tels que valeur[i] + valeur[j] = 239. S’il existe plusieurs paires, choisissez celle avec i minimal, puis j minimal.

Entrée : deux lignes : la liste ci-dessus, puis la ligne cible 239.

Sortie : une ligne : soit i j séparés par un espace, soit le mot NONE si aucune paire.

Contraintes réelles

• Entrée : une seule ligne sur stdin (format indiqué ci-dessus), sans espaces superflus en fin de ligne.
• Sortie : une seule ligne sur stdout, exactement la valeur demandée (pas de texte d’explication).
• python : bibliothèque standard uniquement ; pas d’accès réseau ni de fichiers autres que stdin/stdout.
• Complexité : respecter la borne indiquée dans l’énoncé (souvent O(n) ou O(n²) pour n ≤ 16).

Parcours pédagogique

• Piste : Recherche dans un tableau (serie-n-two-sum) — étape 1 sur cette famille.
• Objectif : Two-sum : indices distincts ou constante NONE.
• Indice global : numéro de défi 1222 / 10000 (famille 22/25, variante 49 / 400).

Indices

• Parsez stdin en types exacts (entier 64 bits signé si nécessaire).
• Testez sur papier avec les petites valeurs du gabarit.
• Vérifiez les cas limites mentionnés.

Solution possible

1. Double boucle O(n²) suffit pour n=10 ; hash map possible pour n plus grand.

Pseudo-code (python)

Copier# lire la ligne stdin → variables
# appliquer l’algorithme décrit
# print(resultat)  # une ligne

Résultat de référence (tests automatisés)

La CI exécute la même logique que ce dépôt sur votre variante : la sortie attendue est exactement :

Copier2 7

Référence (tests automatisés) : 2 7