Joseph Marteau – Épreuve régionale 2025

Niveau 1 ⋅ Validation weight: 100%

Énoncé

Joseph a obtenu une réponse d'un de ses collègues, Joseph Marteau, qui occupe un poste d'horloger dans la cité.

Joseph Marteau lui indique avoir de précieuses informations à lui transmettre, et lui promet de l'aider à condition que Joseph l'aide en retour.

Joseph Marteau a récemment remarqué que ses horloges ne tournent pas assez vite. Il suppose qu'il s'agit d'une erreur du stagiaire précédent lors de l'assemblage des engrenages.

Le premier engrenage est entrainé à vitesse constante par un moteur et chaque engrenage, en fonction de son nombre de dents, influence la rotation du suivant. Aidez Joseph à trouver l’ordre optimal pour que l’horloge maximise la vitesse du dernier engrenage.

Si plusieurs solutions existent, afficher n'importe laquelle d'entre elles.

Pour rappel, si un engrenage possède $D_1$ dents et tourne à une vitesse $v_1$, alors un engrenage relié à celui-ci possédant $D_2$ dents tournera à une vitesse $v_2 = v_1 \times \dfrac{D_1}{D_2}$.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, nombre d'engrenages.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : L, liste des engrenages, représentés par leur nombre de dents.

Sortie

Afficher sur une ligne, et séparés par des espaces, les engrenages par leur nombre de dents dans l'ordre qui permet de maximiser la vitesse du dernier engrenage. Si plusieurs solutions existent, afficher n'importe laquelle d'entre elles.

Contraintes

  • $1 \le N \le 100$
  • $0 \le L_i \le 1\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
15 12 20 18
Exemple de sortie
20 15 18 12
Commentaire

Dans cet exemple, nous disposons de 4 engrenages, ayant respectivement 15 dents, 12 dents, 20 dents et 18 dents.

Supposons de manière arbitraire que le permier engrenage est entraîné à une vitesse de 10 tours par minutes. Cette image montre deux configurations possible des engrenages, et les vitesses associées :

image

Dans la première configuration présentée, 15 12 20 18, tourner la première roue à 10 tours par minutes entraîne une rotation de la dernière roue à environ 8.33 tours par minutes.

Dans la seconde configuration présentée, 20 15 18 12, tourner la première roue à 20 tours par minutes entraîne une rotation de la dernière roue à environ 16.67 tours par minutes.

En supposant que la première roue tourne à une vitesse de 10 tours par minutes, avec les engrenages disponibles ici, il n'est pas possible de faire tourner la dernière roue à plus de 16.67 tours par minutes. La configuration 20 15 18 12 est donc une configuration optimale, et est considérée comme une bonne réponse.

Dans cette situation, arranger les engrengages dans l'ordre 20 18 15 12 aurait également produit une vitesse optimale pour le dernier engrenage. 20 18 15 12 serait donc également une réponse valide.