Coding Solution

The Descent – solution CodinGame en C

Facilegame looplinear searchargmaxgreedyMis à jour le
Réponse courte

À 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

  1. 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.
  2. 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.
  3. 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.
  4. 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é

TempsO(8) par tour
MémoireO(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;
}

Erreurs fréquentes

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome