The Descent – solution CodinGame en C
À chaque tour, on lit les huit hauteurs de montagnes, on cherche l'indice de la plus haute et on l'affiche : le vaisseau tire dessus. Viser systématiquement la plus haute suffit, car c'est toujours elle qui menace le vaisseau en premier. C'est une recherche de maximum (argmax) dans la boucle de jeu.
L'énoncé
Un vaisseau survole huit montagnes en perdant de l'altitude. À chaque tour, il peut tirer sur une montagne, ce qui la fait baisser. S'il touche une montagne, la partie est perdue ; elle est gagnée quand toutes les montagnes sont rasées.
À chaque tour, le jeu envoie huit entiers : les hauteurs des montagnes 0 à 7, entre 0 et 9. Le programme doit répondre par une ligne contenant l'indice de la montagne à viser. La boucle de jeu est infinie : on lit et on répond tour après tour jusqu'à la fin de la partie.
La démarche, étape par étape
- Mettre en place la boucle de jeuLes puzzles de type bot ne s'arrêtent jamais d'eux-mêmes : tout se passe dans un while(true). Chaque itération correspond à un tour, avec huit lignes en entrée et exactement une ligne en sortie.
- Lire les huit hauteursOn lit les huit valeurs à chaque tour, même si on croit déjà connaître la réponse. Sauter des lectures laisse des nombres dans le tampon et décale tous les tours suivants.
- Trouver l'indice du maximumOn retient la plus grande hauteur et son indice pendant la lecture. On initialise le maximum sous toute hauteur possible (-1) pour qu'un tour où tout vaut 0 donne quand même un indice valide.
- Afficher l'indiceOn affiche l'indice, pas la hauteur. Chaque réponse doit se terminer par un retour à la ligne et être envoyée (flush) pour que l'arbitre la reçoive à temps.
Complexité
O(8) par tourO(1)Chaque tour se résume à parcourir huit valeurs, donc un coût constant. Rien à mémoriser d'un tour à l'autre : l'entrée reflète déjà les tirs précédents.
Code de la solution
The Descent – C
#include <stdio.h>
int main()
{
while (1) {
int best = 0, maxH = -1;
for (int i = 0; i < 8; i++) {
int h;
if (scanf("%d", &h) != 1)
return 0;
if (h > maxH) {
maxH = h;
best = i;
}
}
printf("%d\n", best);
fflush(stdout);
}
return 0;
}
The Descent – Java
import java.util.*;
class Player {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
while (true) {
int best = 0, maxH = -1;
for (int i = 0; i < 8; i++) {
int h = in.nextInt();
if (h > maxH) {
maxH = h;
best = i;
}
}
System.out.println(best);
}
}
}
The Descent – Python 3
while True:
heights = [int(input()) for _ in range(8)]
print(heights.index(max(heights)))
Erreurs fréquentes
- Afficher la hauteur au lieu de l'indiceL'arbitre attend un nombre entre 0 et 7. Afficher la hauteur maximale semble cohérent dans les logs mais vise la mauvaise montagne, et le vaisseau s'écrase au bout de quelques tours.
- Ne pas lire toutes les lignesSortir de la boucle de lecture dès qu'on voit un 9 laisse des hauteurs non lues. Au tour suivant, le programme lit des données décalées et tire au hasard.
- Reprendre une vieille solution FIRE/HOLDBeaucoup de tutoriels montrent encore l'ancienne version où l'on répond FIRE ou HOLD selon la position X du vaisseau. Le puzzle actuel rejette immédiatement cette sortie.
- Maximum initialisé à 0 avec une comparaison stricteSi max vaut 0 au départ et qu'on teste h > max, un tour où toutes les montagnes valent 0 ne fixe jamais l'indice. Partir de -1 ou de la première hauteur règle le problème.
Pour aller plus loin
Pourquoi le choix glouton est-il sûr ? Le vaisseau perd régulièrement de l'altitude et chaque tir ne détruit qu'une partie d'une seule montagne : la première qu'il peut percuter est donc toujours la plus haute. En la visant à chaque tour, on fait baisser la hauteur maximale, et une montagne plus basse ne peut jamais devenir plus dangereuse que celle qu'on attaque déjà. Tirer ailleurs revient à perdre un tour pendant que le sommet le plus dangereux se rapproche. En cas d'égalité entre deux montagnes, peu importe laquelle on vise : l'autre deviendra le maximum au tour suivant. Ce raisonnement, « la contrainte qui compte est toujours la valeur extrême », se retrouve plus tard dans des problèmes d'ordonnancement ou dans Horse-racing Duals.
Questions fréquentes
Que faut-il afficher à chaque tour dans The Descent ?
Un seul entier entre 0 et 7 : l'indice de la montagne à viser. Tirer sur la plus haute à chaque tour passe tous les tests.
Pourquoi ma solution FIRE/HOLD ne marche plus ?
Elle a été écrite pour une ancienne version du puzzle. L'arbitre actuel n'envoie que les huit hauteurs et attend un indice, donc FIRE ou HOLD est une action invalide.
Faut-il mémoriser les tours précédents ?
Non. Les hauteurs reçues tiennent déjà compte des tirs précédents, chaque tour se traite donc indépendamment.