Prologin
2024
Énoncé¶
Vous trouvez le concept de faire un concours d'informatique avec trois étapes et plusieurs centaines de participants ridicules pour déterminer un seul gagnant. Vous faites donc appel à l'oracle de Delphes pour connaître le meilleur participant qui gagnerait Prologin 2021.
Pour parvenir à l'oracle de Delphes, vous devez traverser en premier le labyrinthe de Minos, où le Minotaure veille que personne ne passe. Le labyrinthe est composé de $n$ rangées et $n$ colonnes, pour un total de $n^2$ chambres. Vous commencez à la chambre $(1, 1)$, et la sortie du labyrinthe se situe à la chambre $(n, n)$. Heureusement, le Minotaure, après plusieurs millénaires souffre d'arthropathie chronique dégénérative et ne se déplace que quand son odorat détecte un intrus dans le labyrinthe. Doté des capacités divines de Poséidon, le Minotaure, une fois qu'il vous détecte peut se déplacer à une vitesse infinie et il vous sera impossible de lui échapper. Le Minotaure est dans la chambre $(n, 1)$ et son odorat peut vous détecter si vous êtes dans la chambre $(x, y)$ et si $|x - n| + |y - 1| < n - 1$. De plus, craignant le regard cuisant d'Hélios, le dieu du soleil, vous ne pouvez seulement aller de la chambre $(x, y)$ à la chambre $(x + 1, y)$ ou la chambre $(x, y + 1)$. Sinon, vous êtes cuit ! (au sens littéral du terme...)
Une fois le labyrinthe de Minos traversé, vous terminez assez aisément votre trajet. Arrivé à Delphes, la Pythie, depuis peu passionnée d'algorithmique et de mathématiques, décide de vous aider pour votre quête pour déterminer qui va gagner l'édition 2021 du concours Prologin, à condition que vous l'aidiez pour un problème qu'elle tente de résoudre.
En effet, la Pythie vous demande de calculer en premier le nombre de chemins $k$ par lesquels vous auriez pu traverser le labyrinthe de Minos, puis $\sum_{1\leq i\leq k}\sum_{1\leq j\leq k}\text{lcm}(i, j)$, où $\text{lcm}(i, j)$ désigne le plus petit commun multiple des entiers positifs $i$ et $j$.
Sauriez-vous répondre à la Pythie pour pouvoir demander son oracle ?
Entrée¶
- Un entier $n$, le nombre de rangées et de colonnes de chambres dans le labyrinthe de Minos.
Sortie¶
- En premier, l'entier $k$, le nombre de chemins par lesquels vous auriez pu traverser le labyrinthe de Minos.
- Ensuite, sur la deuxième ligne, $\sum_{1\leq i\leq k}\sum_{1\leq j\leq k}\text{lcm}(i, j)$.
Contraintes¶
- $2 ≤ n ≤ 28$