Mars Lander - Episode 1 – solution CodinGame en C
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
- 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.
- 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.
- 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.
- 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.
- 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é
O(H) par tour pour la simulation, O(1) avec la formule ferméeO(N) pour le reliefLa 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;
}
Mars Lander - Episode 1 – Java
Même modèle sous forme fermée : après les 5 tours de montée, la vitesse vaut dY - 8,555 et l'altitude Y - 36,665 + 5*dY, puis la série arithmétique donne le moment où la vitesse atteint -40 ; le nombre de tours est arrondi avec Math.round.
import java.util.*;
import java.math.*;
class Player {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] surfaceX = new int[N];
int[] surfaceY = new int[N];
for (int i = 0; i < N; i++) {
surfaceX[i] = in.nextInt();
surfaceY[i] = in.nextInt();
}
while (true) {
int X = in.nextInt();
int Y = in.nextInt();
int dX = in.nextInt();
int dY = in.nextInt();
in.nextInt(); in.nextInt(); in.nextInt();
// 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 = dY - 8.555;
double vY = Y - 36.665 + 5*dY;
long t = Math.round((-40-vdY)/0.289);
if (vY + t*(vdY+0.289*(1+t)/2) > groundY)
System.out.println("0 0");
else
System.out.println("0 4");
}
}
}
Mars Lander - Episode 1 – Python 3
Formule fermée identique à Java, mais le nombre de tours est arrondi au supérieur avec math.ceil, ce qui est un peu plus prudent.
import math
N = int(input())
surfaceX, surfaceY = [], []
for i in range(N):
landX, landY = [int(j) for j in input().split()]
surfaceX.append(landX)
surfaceY.append(landY)
while 1:
X, Y, dX, dY, fuel, rotate, power = [int(i) for i in input().split()]
# Finds landing altitude by Looking for 2 consecutive points w/ same Y
groundY, i = -1, 0
while (i < N) and (groundY == -1):
if (surfaceX[i] <= X) and (X <= surfaceX[i+1]):
groundY = surfaceY[i]
i+=1
# 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
vdY , vY = dY-8.555, Y-36.665+5*dY;
t = math.ceil((-40-vdY)/0.289);
if (vY + t*(vdY+0.289*(1+t)/2) > groundY):
print(0, 0)
else:
print(0, 4)
Erreurs fréquentes
- Croire que la poussée est instantanéeDemander 4 quand la vitesse atteint -40, c'est trop tard : la puissance passe par 1, 2, 3, 4 pendant que la gravité continue d'accélérer la sonde, et la vitesse dépasse la limite de plusieurs m/s. Prévoyez une marge ou simulez la montée.
- Freiner dès le premier tourPousser à fond dès le départ fonctionne mais brûle du carburant pour rien ; sur les tests à faible réserve, le réservoir se vide en vol et la sonde s'écrase. Freinez tard, pas tôt.
- Se fier à la vitesse arrondieLes vitesses reçues sont des entiers arrondis alors que le jeu vérifie la valeur réelle. Un contrôleur réglé pour toucher le sol à -40 pile peut échouer à -40,4 : gardez une ou deux unités de marge.
- Ne pas lire toutes les valeursChaque tour envoie 7 entiers. Oublier de lire ceux qu'on n'utilise pas (carburant, angle, puissance) décale la lecture et la sonde réagit à de mauvais chiffres au tour suivant.
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.