Coding Solution

Skynet: The Chasm – solution CodinGame en C

Facilesimulationgame loopconditionsphysicsMis à jour le
Réponse courte

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

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

TempsO(1) per turn
MémoireO(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;
}
            

Erreurs fréquentes

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é.

Puzzles similaires

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