Coding Solution

Mars Lander - Episode 1 – solution CodinGame en C

Facilesimulationphysicscontrol loopMis à jour le
Réponse courte

Gardez la sonde verticale (rotation 0) et choisissez à chaque tour entre poussée 0 et poussée 4. La méthode solide consiste à simuler : si j'attends encore un tour puis que je monte la poussée à 4 (elle ne gagne que 1 par tour), ma vitesse verticale au sol restera-t-elle au-dessus de -40 m/s ? Si oui, on continue la chute libre, sinon on pousse à 4. Une règle plus simple, poussée maximale dès que la vitesse passe sous environ -37 m/s, passe aussi tous les tests.

L'énoncé

Une sonde démarre au-dessus d'une zone d'atterrissage plate sur Mars et doit s'y poser sans casse. À chaque tour, vous recevez sa position, ses vitesses horizontale et verticale, le carburant restant, l'angle et la puissance actuels, et vous répondez par un angle et une puissance de 0 à 4.

Dans ce premier épisode, seul le mouvement vertical compte : la sonde descend tout droit, l'angle doit être 0 au contact et la vitesse verticale ne doit pas dépasser 40 m/s. La gravité martienne vaut 3,711 m/s², chaque unité de poussée donne 1 m/s² vers le haut et consomme 1 litre par tour, et la puissance ne varie que de 1 par tour : une commande met donc plusieurs tours à produire tout son effet.

La démarche, étape par étape

  1. Trouver l'altitude du solLisez une fois les points du relief et repérez le segment qui contient l'abscisse X de la sonde ; son Y est l'altitude d'atterrissage. Comme la chute est verticale, elle ne change jamais.
  2. Modéliser un tourÀ chaque tour, la puissance réelle se rapproche de 1 de la valeur demandée, puis vitesse += puissance - 3,711 et altitude += vitesse. À puissance 4, le gain net n'est que de +0,289 m/s par tour : le freinage est lent.
  3. Simuler « j'attends encore un tour »Depuis l'état courant, simulez un tour à puissance 0, puis la montée 1, 2, 3, 4, puis une poussée constante de 4 jusqu'au sol ou jusqu'à ce que la sonde ne tombe plus.
  4. DéciderSi la vitesse simulée au sol reste dans la limite de -40 m/s, on peut attendre : affichez « 0 0 ». Sinon, freinez tout de suite avec « 0 4 ». Attendre le plus longtemps possible, c'est ce qui économise le carburant.
  5. Garder l'angle à 0N'envoyez jamais d'angle non nul : l'atterrissage exige une sonde verticale, et toute inclinaison crée une vitesse horizontale qu'il faudrait ensuite annuler.

Complexité

TempsO(H) par tour pour la simulation, O(1) avec la formule fermée
MémoireO(N) pour le relief

La version C simule tour par tour jusqu'au sol (quelques dizaines d'itérations), tandis que Java et Python remplacent cette boucle par la somme arithmétique de la phase à poussée constante.

Code de la solution

Mars Lander - Episode 1 – C

Simulation littérale : 5 tours de montée en puissance, puis +0,289 m/s par tour jusqu'au sol ou jusqu'à l'arrêt de la chute, et comparaison de la vitesse finale à -40.

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char** argv)
{
    int N;
    scanf("%d\n", &N);

    int surfaceX[N];
    int surfaceY[N];
    for (int i = 0; i < N; i++)
        scanf("%d %d\n", &surfaceX[i], &surfaceY[i]);

    while (1) {
        int X, Y, dX, dY, fuel, rotate, power;
        scanf("%d %d %d %d %d %d %d", &X, &Y, &dX, &dY, &fuel, &rotate, &power);
        
        // Finds landing altitude by Looking for 2 consecutive points w/ same Y
        int groundY = -1;
        for (int i = 0; (i < N && groundY == -1); i++)
            if (surfaceX[i] <= X && X <= surfaceX[i+1])
                groundY = surfaceY[i];

        /* Finds out if it is safe to start braking only next turn, by
           simulating it and analyzing vertical speed at landing
           If it is safe, waits, else starts braking*/
        double vdY = (double)dY;
        double vY = (double)Y;
        for (double i = 0.0; i <= 4; i++) {
            vdY += i - 3.711;
            vY += vdY;
        }
        while (vY > groundY && vdY < 0) {
            vdY += 0.289; // 4-3.711;
            vY += vdY;
        }
        printf((vdY >= 0 || vdY > -40.0) ? "0 0\n" : "0 4\n");
    }
    return EXIT_SUCCESS;
}
            

Erreurs fréquentes

Pour aller plus loin

Un petit raisonnement montre pourquoi freiner le plus tard possible est optimal. Sur T tours, la variation de vitesse verticale vaut la somme des puissances moins 3,711*T, donc le carburant consommé vaut (v_finale - v_initiale) + 3,711*T. Pour l'économiser, il faut toucher le sol aussi vite que permis (v_finale proche de -40) et rester le moins de tours possible en l'air : chute libre d'abord, puis freinage à pleine puissance au dernier moment sûr. C'est exactement la stratégie « tout ou rien » codée ici, et la même routine de prédiction resservira dans les épisodes 2 et 3 une fois le mouvement horizontal maîtrisé. La règle du seuil fixe finit par consommer à peu près autant, car la puissance oscille autour de la limite une fois à 4, mais elle n'offre aucune garantie si la vitesse de départ est déjà élevée.

Questions fréquentes

Quelle est la solution la plus simple pour Mars Lander épisode 1 ?

Afficher « 0 4 » quand la vitesse verticale passe sous environ -37 m/s, et « 0 0 » sinon. La marge compense la montée en puissance limitée à 1 par tour.

Pourquoi ne peut-on pas régler directement la puissance voulue ?

Le jeu ne laisse varier la puissance que de 1 par tour : la valeur envoyée est une consigne. Il faut anticiper les quelques tours nécessaires pour l'atteindre.

Les points du relief servent-ils dans l'épisode 1 ?

Pas obligatoirement, puisque la sonde est déjà au-dessus de la zone plate, mais connaître l'altitude du sol permet de prédire précisément la vitesse d'impact au lieu de dépendre d'un seuil fixe.

Puzzles similaires

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