Coding Solution

The Paranoid Android – solution CodinGame en C

Moyensimulationgreedygame loopinput parsingMis à jour le
Réponse courte

On mémorise, pour chaque étage, la colonne que les clones doivent atteindre : la position de l'ascenseur à chaque étage et celle de la sortie à l'étage de sortie. Chaque tour, on ne regarde que le clone de tête : s'il marche vers la gauche alors que sa cible est à sa droite, ou vers la droite alors qu'elle est à sa gauche, on répond BLOCK ; dans tous les autres cas, y compris quand il n'y a aucun clone (étage -1), on répond WAIT.

L'énoncé

Des clones sortent d'un générateur à l'étage du bas l'un après l'autre et marchent en ligne droite, ne faisant demi-tour que lorsqu'ils rencontrent un clone bloqué. Chaque étage possède un ascenseur qui monte un clone à l'étage supérieur, et la sortie se trouve au dernier étage. On connaît le nombre d'étages, la largeur de la zone, le nombre de tours, la position de la sortie, le nombre de clones disponibles et la position de chaque ascenseur.

Chaque tour, on reçoit l'étage, la position et la direction du clone de tête (ou -1 -1 NONE s'il n'y en a aucun) et on répond WAIT ou BLOCK. Un clone bloqué reste sur place comme un mur qui renvoie les autres. Il faut amener au moins un clone à la sortie avant d'épuiser les tours ou les clones.

La démarche, étape par étape

  1. Lire toute la ligne d'initialisationLa première ligne contient huit entiers ; seuls le nombre d'étages, l'étage de sortie et la position de la sortie comptent pour cet épisode. On lit ensuite une ligne par ascenseur et on stocke sa position indexée par étage.
  2. Définir une cible par étagetarget[f] est la colonne de l'ascenseur à l'étage f, et target[exitFloor] celle de la sortie. Avec ce tableau, chaque étage devient le même sous-problème : atteindre une colonne connue.
  3. Décider uniquement sur le clone de têteSi le clone va vers LEFT avec pos < target, ou vers RIGHT avec pos > target, il s'éloigne de son but : on le bloque. Le clone suivant viendra buter contre lui et repartira dans la bonne direction.
  4. Attendre dans tous les autres casQuand le clone se dirige déjà vers sa cible, se trouve dessus, ou quand il n'y a pas de clone de tête (étage -1), on répond WAIT. On ne bloque jamais un clone situé sur sa colonne cible : il est sur le point de prendre l'ascenseur.

Complexité

TempsO(1) per turn
MémoireO(F)

Après une préparation en O(F) pour les cibles par étage, chaque tour se réduit à une comparaison. F est le nombre d'étages.

Code de la solution

The Paranoid Android – C

#include <stdio.h>

int main(void) {
    int nbFloors, width, nbRounds, exitFloor, exitPos, nbClones, nbAddElevators, nbElevators;
    scanf("%d %d %d %d %d %d %d %d", &nbFloors, &width, &nbRounds, &exitFloor,
          &exitPos, &nbClones, &nbAddElevators, &nbElevators);

    /* target[f] = column the leading clone must reach on floor f */
    int target[nbFloors];
    target[exitFloor] = exitPos;
    for (int i = 0; i < nbElevators; i++) {
        int f, pos;
        scanf("%d %d", &f, &pos);
        target[f] = pos;
    }

    while (1) {
        int floor, pos;
        char dir[11];
        scanf("%d %d %10s", &floor, &pos, dir);

        /* block only a clone that walks away from its target */
        if (floor >= 0 && ((dir[0] == 'L' && pos < target[floor]) ||
                           (dir[0] == 'R' && pos > target[floor])))
            printf("BLOCK\n");
        else
            printf("WAIT\n");
        fflush(stdout);
    }
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

Une seule comparaison suffit parce que tous les clones quittent le générateur dans la même direction et la conservent quand ils prennent un ascenseur. Chaque étage n'est donc abordé qu'une fois par le clone de tête, et au plus un BLOCK par étage est nécessaire : soit le clone arrive face à sa cible et y va tout droit, soit il arrive dos à elle et un seul sacrifice retourne tous ceux qui le suivent. On obtient ainsi une borne d'un clone sacrifié par étage, ce qui explique que cette règle gloutonne tienne dans le budget de clones des tests. La suite difficile, « The Paranoid Android - One step further », casse cette propriété : certains étages ont plusieurs ascenseurs ou aucun, et il faut en construire, si bien que le problème devient une recherche de plus court chemin sur des états (étage, position, direction).

Questions fréquentes

Pourquoi ne regarder que le clone de tête ?

Les clones qui suivent le leader empruntent le même chemin quelques cases plus tard. Ce qu'on fait au leader (le laisser passer ou le bloquer) décide de la direction de tout le groupe à cet étage.

Que signifie la direction NONE ?

Elle accompagne l'étage -1 et la position -1 quand aucun clone ne marche, typiquement au départ ou juste après un blocage. On répond WAIT et le clone suivant apparaît.

Quelle différence avec « One step further » ?

Dans la suite, on peut construire des ascenseurs supplémentaires et certains étages en ont plusieurs ou aucun : la règle gloutonne « bloquer s'il s'éloigne » ne suffit plus et il faut une recherche dans un graphe.

Puzzles similaires

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