Skynet: The Chasm – solution CodinGame en C
La vitesse minimale qui franchit un trou de G cases est G + 1, et garder exactement cette vitesse rend l'arrêt sur la plateforme d'atterrissage facile. Chaque tour : SLOW si l'on a dépassé le trou ou si l'on va plus vite que G + 1, SPEED si l'on va moins vite que G + 1, JUMP quand un saut depuis la case courante retombe au-delà du trou (x + speed >= road + gap), et WAIT sinon.
L'énoncé
Une moto roule sur une route droite de R cases, suivie d'un trou de G cases et d'une plateforme d'atterrissage de L cases. Au départ, on reçoit ces trois longueurs ; puis chaque tour, on reçoit la vitesse et la position courantes de la moto et on répond SPEED, SLOW, JUMP ou WAIT.
La vitesse varie d'une unité par commande et la moto avance de sa vitesse à chaque tour. Elle doit franchir le trou d'un saut puis s'arrêter complètement (vitesse 0) avant la fin de la plateforme.
La démarche, étape par étape
- Choisir la vitesse cibleUn saut depuis la dernière case de route (x = R - 1) retombe en x + speed, donc il atteint la plateforme quand speed >= G + 1. On vise exactement G + 1 : toute vitesse supplémentaire ne fait que compliquer le freinage sur une plateforme courte.
- Freiner après le trouDès que x >= R + G, la moto est sur la plateforme : on répond SLOW à chaque tour jusqu'à l'arrêt. La même commande SLOW gère aussi le cas où la moto démarre plus vite que G + 1.
- Accélérer avant le trouTant que la vitesse est inférieure ou égale à G, on répond SPEED. Dans tous les tests, la route est assez longue pour atteindre la vitesse nécessaire.
- Sauter au bon momentÀ la vitesse G + 1, on saute dès que x + speed >= R + G, ce qui à cette vitesse correspond à x = R - 1, la dernière case avant le trou. Sinon, on répond WAIT et on conserve la vitesse.
Complexité
O(1) per turnO(1)Chaque tour tient en quelques comparaisons sur la vitesse et la position courantes ; rien n'est conservé d'un tour à l'autre.
Code de la solution
Skynet: The Chasm – C
Les versions C, Java et Python partagent la même chaîne ordonnée de conditions. L'ordre compte : le test « trou dépassé ou trop rapide » vient en premier pour que la moto freine toujours sur la plateforme, avant que le test de vitesse ne la pousse à accélérer.
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char** argv)
{
int before, gap, after;
scanf("%d%d%d\n", &before, &gap, &after);
for (;;) {
// x = motorbike abscissa ; dx = motorbike speed
int dx, x;
scanf("%d%d", &dx, &x);
// if the bike has passed the gap, or going faster than needed to jump over it
/* past the gap: brake to 0 on the platform; too fast: lose speed before the jump */
if (x >= before+gap || dx > gap+1)
printf("SLOW\n");
// if the bike isn't going fast enough to jump over the gap
else if (dx <= gap)
printf("SPEED\n");
// if the bike can land after the gap by jumping
/* here dx == gap+1, so the jump lands on the first platform cell or later */
else if (x+dx >= before+gap)
printf("JUMP\n");
else
printf("WAIT\n");
}
return EXIT_SUCCESS;
}
Skynet: The Chasm – Java
Même chaîne de décision que le code C, avec lecture par Scanner et une commande affichée par tour. Les variables before, gap et after correspondent à road, gap et platform.
import java.util.*;
class Player {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int before = in.nextInt();
int gap = in.nextInt();
int after = in.nextInt();
while (true) {
// x = motorbike abscissa ; dx = motorbike speed
int dx = in.nextInt();
int x = in.nextInt();
// if the bike isn't going fast enough to jump over the gap
if ((x >= before + gap) || (dx > gap + 1))
System.out.println("SLOW");
// if the bike is going slower than needed : speed
else if (dx <= gap)
System.out.println("SPEED");
// if the bike can land after the gap : jump
else if (x + dx >= before + gap)
System.out.println("JUMP");
else
System.out.println("WAIT");
}
}
}
Skynet: The Chasm – Python 3
Même logique en Python ; les entrées arrivent une valeur par ligne, donc chaque tour fait deux appels int(input()), la vitesse d'abord puis la position.
# road length, gap length, landing platform length (one value per line)
before, gap, after = int(input()), int(input()), int(input())
while 1:
# x = motorbike abscissa ; dx = motorbike speed
dx, x = int(input()), int(input())
# if the bike is after the gap, or going faster than needed : slow
# minimum speed to clear the gap is gap + 1: never go faster than that
if (x >= before + gap) or (dx > gap+1):
print("SLOW")
# if the bike isn't going fast enough to jump over the gap
elif (dx <= gap):
print("SPEED")
# if the bike can land after the gap by jumping
# at speed gap + 1 this is true only on the last road cell, x = before - 1
elif (x+dx >= before+gap):
print("JUMP")
else:
print("WAIT")
Erreurs fréquentes
- Sauter trop tôtRépondre JUMP dès que la vitesse est bonne, où que soit la moto, la fait retomber dans le trou. La condition de saut doit faire intervenir la position : x + speed doit atteindre R + G.
- Aller plus vite que nécessaireAccélérer au maximum paraît sûr pour le saut, mais la moto a ensuite besoin de nombreux tours pour freiner et dépasse les plateformes courtes. Il faut plafonner la vitesse à G + 1.
- Tester la vitesse avant la positionSi « vitesse trop basse, accélérer » est testé avant « trou déjà dépassé », la moto continue d'accélérer sur la plateforme. Le test d'après-trou doit venir en premier.
- Lire les entrées sur une seule ligneRoute, trou et plateforme arrivent sur trois lignes distinctes, de même que la vitesse et la position à chaque tour. Un input().split() en Python sur une seule ligne lève une erreur dès le premier tour.
Pour aller plus loin
La seule condition subtile est le saut, et l'écrire x + speed >= R + G plutôt que x == R - 1 rend la règle explicite : un saut est utile exactement quand son point de chute dépasse le trou. À la vitesse cible G + 1, les deux formulations coïncident, mais la version générale explique aussi pourquoi les tests sont construits ainsi : à cette vitesse, la moto n'a qu'une seule case d'où le saut réussit, donc les cas officiels font en sorte que la moto, en accélérant d'une unité par tour, passe par R - 1. Pour un bot plus robuste, calculez à l'avance combien de tours d'accélération et d'attente vous amènent exactement en R - 1, ou acceptez une vitesse légèrement plus élevée pour que davantage de cases conviennent, à condition que la plateforme permette de freiner : s'arrêter depuis une vitesse s prend s tours et couvre environ s(s - 1) / 2 cases de plus. C'est un bon échauffement pour Skynet: The Bridge, où plusieurs motos et des trous transforment le même raisonnement en une recherche.
Questions fréquentes
Quelle vitesse faut-il pour franchir le trou ?
Au moins gap + 1, car le saut part de la dernière case de route et doit retomber sur la première case de la plateforme ou au-delà. Garder exactement gap + 1 est le plus sûr pour le freinage.
Quand envoyer JUMP ?
Quand la position courante plus la vitesse courante atteint road + gap. À la vitesse gap + 1, cela arrive sur la dernière case de route, x = road - 1.
Pourquoi ma moto tombe-t-elle au bout de la plateforme ?
Elle va trop vite. Chaque SLOW ne réduit la vitesse que d'une unité : il faut limiter la vitesse à gap + 1 avant le saut et freiner à chaque tour une fois posé.