Bonjour

Je coince sur ce problème

Des spéléologues ont découvert une immense galerie creusée il y a des millions d'années par une rivière souterraine. La galerie est magnifique et il a été décidé de l'ouvrir au public. Cependant, l'arrivée de nombreux visiteurs risque d'entraîner une corrosion des parois du fait d'un excès de dioxyde de carbone. Un système évolué de régénération de l'atmosphère doit donc être mis en place pour la protéger. Un certain nombre de conduits d'aération vont ainsi être percés à intervalles réguliers le long de la galerie.

On vous donne la description de la galerie sous la forme d'une grille rectangulaire de nombres, les cases de la galerie étant marquées par des 0 et les cases de roche par des 1. Le couloir de la galerie a toujours une largeur de 1 case et hormis l'entrée et la sortie, chaque case marquée par un 0 a exactement deux de ses quatre cases voisines qui sont marquées par un 0 (deux cases sont voisines si elles ont un côté en commun). L'entrée de la galerie est la case en haut à gauche de la grille, et la sortie est la case en bas à droite.

Étant donné la distance D à respecter entre chaque conduit d'aération, vous devez fournir les coordonnées de toutes les cases où creuser une aération, dans l'ordre le long de la galerie. Le premier conduit d'aération doit se trouver sur la D+1^e case de la galerie en partant de l'entrée, la suivante sur la (D+1)*2^e case, et ainsi de suite.

L'illustration ci-dessus représente une grille de 11 colonnes et 9 lignes. Les cercles rouges représentent les positions où placer des conduits d'aération, si le nombre de cases de galeries à laisser entre deux conduits est de 7. Ainsi, les conduits sont placés à la 8^e case rencontrée en parcourant la galerie depuis l'entrée, puis à la 16^e, la 24^e, la 32^e, et enfin la 40^e.

Limites de temps et de mémoire (C++)

• Temps : 1 s sur une machine à 1 GHz.
• Mémoire : 16 000 ko.

Contraintes

Entrée

Sortie

9 11 7
0 0 1 0 0 0 1 1 1 1 1
1 0 0 0 1 0 1 0 0 0 0
1 1 1 1 1 0 1 0 1 1 0
1 1 0 0 0 0 1 0 0 1 0
1 1 0 1 1 1 1 1 0 1 0
1 1 0 1 1 1 1 0 0 1 0
1 1 0 0 0 0 1 0 1 0 0
1 1 1 1 1 0 1 0 1 0 1
1 1 1 1 1 0 0 0 1 0 0

0 5
5 2
8 7
2 7
5 10

#include <iostream>
#include <array>
#include <vector>
#include <utility>

using Grotte = std::vector<std::vector<int>>;

std::array<std::array<int, 2>, 4> direction
{
  -1, 0,
  0, 1,
  1, 0,
  0, -1
};

int compteur{0}, tmp{0};
std::vector<std::pair<int, int>> sortie;

//Prototypes Fonctions
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c);
bool dansPlateau(int lin, int col, int l, int c);

int main()
{
  std::ios::sync_with_stdio(false);
  int L{0}, C{0};
  std::cin >> L >> C >> compteur;

  Grotte lab;

  for (int i{0}; i < L; ++i)
  {
    lab.push_back(std::vector<int>(C));
    for (int j{0}; j < C; ++j)
    {
      std::cin >> lab [i][j];
    }
  }
  std::cout << "----------------------------------------\n";

  for (int i{0}; i < L; i++)
  {
    for (int j{0}; j < C; j++)
    {
      /*  if (lab [i][j] == 4 || lab [i][j] == 2)
       {
         std::cout << "\033[38;5;11m" << lab [i][j] << " ";
         std::cout << "\033[0m";
       } */
      if (lab [i][j] == 1)
      {
        std::cout << "\033[31m" << lab [i][j] << " ";
        std::cout << "\033[0m";
      }
      else
      {
        std::cout << "\033[38m" << lab [i][j] << " ";
        std::cout << "\033[0m";
      }
    }
    std::cout << "\n";
  }
  std::cout << "----------------------------------------\n";
  if (chemin(lab, 0, 0, 0, L, C))
  {
    for (int i{(int)sortie.size() - 1}; i >= 0; --i)
      std::cout << sortie [i].first << " " << sortie [i].second << '\n';

    std::cout << "----------------------------------------\n";
    for (int i{0}; i < L; i++)
    {
      for (int j{0}; j < C; j++)
      {
        if (lab [i][j] == 7)
        {
          std::cout << "\033[32m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
        else if (lab [i][j] == 5)
        {
          std::cout << "\033[31m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
        else
        {
          std::cout << "\033[38m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
      }
      std::cout << "\n";
    }
  }
  else
    std::cout << "Pas de solution" << std::endl;

  return 0;
}
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c)
{
  int nx{0}, ny{0}, i{0};
  if (x == l - 1 && y == c - 1)
    return true;

  if (dansPlateau(x, y, l, c) && grille [x][y] == 0)
  {
    for (; i < 4; ++i)
    {
      if (i != (olddir + 2) % 4)
      {
        nx = x + direction [i][0];
        ny = y + direction [i][1];
        if (chemin(grille, nx, ny, i, l, c))
        {
          tmp++;
          if (tmp == compteur + 1)
          {
            tmp = 0;
            grille [nx][ny] = 7;
            sortie.push_back({nx, ny});
          }
          else
            grille [nx][ny] = 5;

          return true;
        }

      }
    }
  }
  return false;
}

bool dansPlateau(int lin, int col, int l, int c)
{
  return ((lin >= 0) && (lin < l) && (col >= 0) && (col < c));
}

Pas compris le bug. Tu as quel resultat et tu attends quel resultat ?

Et le probleme avec france ioi, c'est que c'est la galère a debuger, parce qu'il n'y a pas de tests et pas les resultats intermediaires en general.

-
Edité par gbdivers 6 avril 2022 à 20:47:04

Pour la grille

9 11 7

0 0 1 0 0 0 1 1 1 1 1

1 0 0 0 1 0 1 0 0 0 0

1 1 1 1 1 0 1 0 1 1 0

1 1 0 0 0 0 1 0 0 1 0

1 1 0 1 1 1 1 1 0 1 0

1 1 0 1 1 1 1 0 0 1 0

1 1 0 0 0 0 1 0 1 0 0

1 1 1 1 1 0 1 0 1 0 1

1 1 1 1 1 0 0 0 1 0 0

le programme donne en sortie

0 3

3 2

8 5

3 8

3 10

au lieu de 

0 5
5 2
8 7
2 7
5 10

j'ai un décalage pour la première paire 0 - 3 au lieu de 0 - 5

Ensuite mon programme respecte bien la bonne sortie avec 7 de décalage mais en partant de 0 - 3

Donc c'est pas évident à débugger car comme tu dis il ne donne pas les résultats intermédiaires

-
Edité par Duncan4031 6 avril 2022 à 21:33:12

Et France IOI n'est pas toujours clair dans ses explications. C'est quoi en haut et à gauche?
J'ai déjà vu ce problème en Python.
À partir de quelle position commence-t-on à compter? (0, 0)? Ou avant l'entrée?
La case (0, 0) est-elle la première des D premières positions avant le puits d'aération?
Ou bien est-ce que compteur doit passer de 0 à 1 à la seconde position ou de 1 à 2?

Puisque tu n'as pass de boucle dans le tracé, tu n'auras pas de backtracking à faire.
Je cherche ensuite la (seule) position à 0 (array direction).
Je me déplace sur la position et je la marque avec quelque chose de différent de 0 ou 1 (2 par exemple)
J'avance mon compteur en accord.
À mon avis, tu n'as besoin que de la fonction qui valide les coordonnées.

Ta fonction chemin récursive risque de te coûter cher. France IOI est assez strict sur le temps limite.

Ça se fait dans une boucle do ... while se terminant quand on a atteint la sortie.

Inutile d'accumuler les résultats, affiches quand tu les trouves.

Je marquerais donc (0, 0) avec un 2 et je mettrais le compteur à 1.

Je chercherais ensuite dans la boucle le suivant.

-
Edité par PierrotLeFou 7 avril 2022 à 3:35:57

un seul exemple est donné

9 11 7
0 0 1 0 0 0 1 1 1 1 1
1 0 0 0 1 0 1 0 0 0 0
1 1 1 1 1 0 1 0 1 1 0
1 1 0 0 0 0 1 0 0 1 0
1 1 0 1 1 1 1 1 0 1 0
1 1 0 1 1 1 1 0 0 1 0
1 1 0 0 0 0 1 0 1 0 0
1 1 1 1 1 0 1 0 1 0 1
1 1 1 1 1 0 0 0 1 0 0

En sortie

0 5
5 2
8 7
2 7
5 10

5 5 1 5 5 7 1 1 1 1 1 
1 5 5 5 1 5 1 5 5 5 5 
1 1 1 1 1 5 1 7 1 1 5 
1 1 5 5 5 5 1 5 5 1 5 
1 1 5 1 1 1 1 1 5 1 5 
1 1 7 1 1 1 1 5 5 1 7 
1 1 5 5 5 5 1 5 1 5 5 
1 1 1 1 1 5 1 5 1 5 1 
1 1 1 1 1 5 5 7 1 5 0

Je l'ai essayé en C, il passe tous les tests sauf le Test 2. (Je suppose que ça doit être un cas particulier, mais j'ai aucune idée de quoi ?)

Edit, nouveau code : celui la passe à 100% (Je ne le laisse que quelque heures, vu que  France IOI ne diffuse pas les corrigés si on a pas trouvé).

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

enum Dir {EST, SUD, OUEST, NORD};

int **CreateTab2D(int d1, int d2)
{
    int i = 0;
    int *buffer = malloc(sizeof(*buffer) * d1 * d2);
    int **tab = malloc(sizeof(**tab) * d1);
    for(i=0; i<d1; i++)  tab[i] = buffer+(i*d2);

    return tab;
}

int main(void)
{
    int ligne;
    int col;
    int pas;
    scanf("%d%d%d", &ligne, &col, &pas);

    int **tab = CreateTab2D(ligne, col);

    for(int i=0; i<ligne; i++)
        for(int j=0; j<col; j++)
            scanf("%d", &tab[i][j]);

    int x=0;
    int y=0;
    int cpt=0;
    enum Dir dir=OUEST;

    if(pas==0) printf("%d %d\n", 0, 0);

    while(x!=col-1 || y!=ligne-1)
    {
        if(x<col-1 && tab[y][x+1]==0 && dir!=EST)
        {
            x++;
            dir=OUEST;
            cpt++;
            if(cpt>=pas)
            {
                printf("%d %d\n", y, x);
                cpt=-1;
            }
        }
        else if(y<ligne-1 && tab[y+1][x]==0 && dir!=SUD)
        {
            y++;
            dir=NORD;
            cpt++;
            if(cpt>=pas)
            {
                printf("%d %d\n", y, x);
                cpt=-1;
            }
        }
        else if(x>0 && tab[y][x-1]==0 && dir!=OUEST)
        {
            x--;
            dir=EST;
            cpt++;
            if(cpt>=pas)
            {
                printf("%d %d\n", y, x);
                cpt=-1;
            }
        }
        else if(y>0 && tab[y-1][x]==0 && dir!=NORD)
        {
            y--;
            dir=SUD;
            cpt++;
            if(cpt>=pas)
            {
                printf("%d %d\n", y, x);
                cpt=-1;
            }
        }
    }
    return 0;
}

J'ai pas testé les malloc ni libéré la mémoire, c'était juste pour testé sur France IOI

-
Edité par rouIoude 7 avril 2022 à 17:45:26

// Version: travaillons notre C++

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>

bool valide(int l, int c, int L, int C) {
    return 0<=l && l<L && 0<=c && c<C;
}

std::array<std::array<int, 2>, 4> directions {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};

struct Galerie {
    Galerie(std::size_t L_, std::size_t C_) : L(L_), C(C_), m_buffer(L*C) {}
    Galerie(std::size_t L_, std::size_t C_, std::istream &is) : Galerie(L_, C_) {
        for (std::size_t i=0; i < L*C && is >> m_buffer[i] ; ++i)
        { }
    }

    int const& operator()(std::size_t l, std::size_t c) const {
        return m_buffer[offset(l,c)];
    }
    int      & operator()(std::size_t l, std::size_t c)       {
        return m_buffer[offset(l,c)];
    }

    bool est_la_suite(int l, int c) const {
        return valide(l, c, L, C)
            && (*this)(l, c) == 0;
    }
private:
    std::size_t offset(std::size_t l, std::size_t c) const {
        assert(l < L);
        assert(c < C);
        return c + l * C;
    }

    std::size_t      L;
    std::size_t      C;
    std::vector<int> m_buffer;
};

int main() {
    std::size_t L, C, D;
    std::cin >> L >> C >> D;
    Galerie galerie(L, C, std::cin);

    std::size_t l = 0;
    std::size_t c = 0;
    std::size_t d = 1;
    do {
        galerie(l,c) = 2;
        auto const wh = std::find_if(begin(directions), end(directions),
                [l,c,&galerie](auto const& p){ return galerie.est_la_suite(l+p[0], c+p[1]); });
        assert(wh != end(directions));
        auto const [il, ic] = *wh;
        l += il;
        c += ic;
        d++;
        if(d == D+1) {
            std::cout << l << " " << c << '\n';
            d = 0;
        }
    } while(l != L-1 || c != C-1);
    return 0;
}
// Vim: let $CXXFLAGS='-std=c++17 -Wall -Wextra'

PierrotLeFou a écrit:

@rouIoude: on est dans la catégorie sur C++

Je sais !

J'ai passé ton code à la moulinette, le Test 2 ne passe pas comme moi à mon premier essais. 

lmghs a écrit:

Ta solution m'a inspiré...

La moulinette ne prend pas le C++17

C'est encore trop pour ma petite tête ...
J'ai fait la correction pour la définition de directions.
Je ne sais pas si mon code passerait tous les tests.

edit: il ne passe pas le test 2? Est-ce que France IOI dit pourquoi?

Ne marche pas? ...

Vitesse? Ce code-ci est-il mieux?

Mémoire? Des array de dimensions maximum seraient-elles mieux? On pourrait aussi gagner en vitesse.

J'essaie d'optimiser la vittesse en choisissant au mieux l'ordre des choix des directions.
-
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
bool valide(int l, int c, int L, int C) {
    return 0<=l && l<L && 0<=c && c<C;
}
int main(void) {
    // Je privilégie le bas et la droite même si toutes les directionss sont possibles.
    std::array<std::array<int, 2>, 4> directions = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}};
    std::vector<std::vector<int>> galerie;
    int L, C, D;
    std::cin >> L >> C >> D;
    // Je favorise la dimension la plus grande, lignes vs colonnes
    if(C > L) {
        std::swap(directions[0], directions[1]);
        std::swap(directions[2], directions[3]);
    }
    galerie.resize(L);
    for(int l (0); l < L; l++) {
        galerie[l].resize(C);
        for(int c (0); c < C; c++) {
            std::cin >> galerie[l][c];
        }
    }
    int l = 0;
    int c = 0;
    int d = 1;
    do {
        galerie[l][c] = 2;
        int il, ic;
        for(auto dir: directions) {
            il = dir[0];
            ic = dir[1];
            if(valide(l+il, c+ic, L, C) && galerie[l+il][c+ic] == 0) break;
        }
        l += il;
        c += ic;
        d++;
        if(d == D+1) {
            std::cout << l << " " << c << std::endl;
            d = 0;
        }
    } while(l != L-1 || c != C-1);
    return 0;
}

-
Edité par PierrotLeFou 7 avril 2022 à 19:33:20

rouIoude a écrit:

lmghs a écrit:

Ta solution m'a inspiré...

La moulinette ne prend pas le C++17

C'est pour cela que je partage... (NB: ceci dit j'ai essentiellement adapté de code de Pierrot (=> mêmes problèmes plausibles), et ce n'est pas si compliqué à downgrader les lignes 58-60 en C++14)

EDIT/PS: quand il y a des problèmes de vitesse sur france ioi, ce n'est pas jamais un soucis d'alloc (quoique tu as été violent avec de l'allocation 2D) ou de micro-optims. C'est toujours un problème de complexité

-
Edité par lmghs 7 avril 2022 à 19:40:55

PierrotLeFou a écrit:

edit: il ne passe pas le test 2? Est-ce que France IOI dit pourquoi?

Il ne dit pas pourquoi, mais à priori c'est un test ou le pas est de 0. (Une aération toutes les cases !) C'est en rajoutant ça que je l'ai passé !

lmghs a écrit:

ce n'est pas si compliqué à downgrader les lignes 58-60 en C++14)

Il ne prend pas le c++14 non plus, je l'ai converti en C++11, Le test 2 ne passe pas comme tu t'en doutais : 

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>

bool valide(int l, int c, int L, int C) {
    return 0<=l && l<L && 0<=c && c<C;
}

std::array<std::array<int, 2>, 4> directions {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};

struct Galerie {
    Galerie(std::size_t L_, std::size_t C_) : L(L_), C(C_), m_buffer(L*C) {}
    Galerie(std::size_t L_, std::size_t C_, std::istream &is) : Galerie(L_, C_) {
        for (std::size_t i=0; i < L*C && is >> m_buffer[i] ; ++i)
        { }
    }

    int const& operator()(std::size_t l, std::size_t c) const {
        return m_buffer[offset(l,c)];
    }
    int      & operator()(std::size_t l, std::size_t c)       {
        return m_buffer[offset(l,c)];
    }

    bool est_la_suite(int l, int c) const {
        return valide(l, c, L, C)
            && (*this)(l, c) == 0;
    }
private:
    std::size_t offset(std::size_t l, std::size_t c) const {
        assert(l < L);
        assert(c < C);
        return c + l * C;
    }

    std::size_t      L;
    std::size_t      C;
    std::vector<int> m_buffer;
};

int main() {
    std::size_t L, C, D;
    std::cin >> L >> C >> D;
    Galerie galerie(L, C, std::cin);

    std::size_t l = 0;
    std::size_t c = 0;
    std::size_t d = 1;
    do {
        galerie(l,c) = 2;
        auto const wh = std::find_if(begin(directions), end(directions),
                [l,c,&galerie](std::array<int, 2> const& p){ return galerie.est_la_suite(l+p[0], c+p[1]); });
        assert(wh != end(directions));

        int il = (*wh)[0];
        int ic = (*wh)[1];
        l += il;
        c += ic;

        d++;
        if(d == D+1) {
            std::cout << l << " " << c << '\n';
            d = 0;
        }
    } while(l != L-1 || c != C-1);
    return 0;
}

Salut,

Perso, j'ai décidé de prendre le problème sous un autre angle:

D'abord, j'ai décidé de "linéariser" la grille représentant le sous-sol, ce qui fait que, au lieu de le représenter sous la forme d'un std::vector<std::vector<in>>, je l'ai simplement représenté sous la forme d'un std::vector<int> dont la taille totale est -- dés le départ -- définie à NOMBRE_DE_LIGNES * NOMBRE_DE_COLONNES.

Cela n'a l'air de rien, mais comme nos amis de FranceIOI tiennent généralement à  avoir quelque chose de rapide, cela devrait nous permettre de maintenir les données en mémoire d'une manière un peu plus "cache friendly" pour le processeur

Seulement, pour cela, il fallait disposer d'un moyen -- finalement tout simple -- afin de pouvoir déterminer l'indice dans ce tableau linéaire auquel correspond une position donnée.

Cela peut se faire très facilement avec la formule indice_recherché = LIGNE_ACTUELLE * NOMBRE_DE_COLONNES + COLONNE_ACTUELLE, formule utilisée par la fonction toIndiex de mon code

D'un autre coté, il faut aussi pouvoir récupérer la position dans la grille (en ligne et colonne) à laquelle correspond un indice donné dans le tableau linéaire. 

Les deux formules à utiliser ne sont finalement pas plus compliquées que la première vu qu'elles sont respectivement

• ligne_recherchée  = indice_courent / NOMBRE_DE_COLONNES et
• colonne_recherchée = indice_courent modulo NOMBRE_DE_COLONNES

Ce sont ces deux formules qui permettent à la fonction fromIndex renvoyer une valeur correspondant à la ligne et une valeur correspondant à la colonne.

Et, parce que j'aime vraiment bien les choses "bien rangées", j'ai créé deux structures de données de base:

la structure Dimensions qui se contente de garder le nombre de lignes, le nombre de colonnes et le nombre d'éléments total que cela représente

et la structure GroundMap, qui représente le "sous-sol" tel qu'il a été cartographié

J'en ai profité, par facilité, pour garder en mémoire le nombre de "points de galeries" lorsque la carte est chargée, car cela me facilitera la vie par la suite

Puis, je me suis dit que les seuls points de la carte qui m'intéressent sont ceux où il est possible de passer, car je n'ai vraiment pas encore une âme de passe-muraille

Et, bien sur, il faut les avoir les points dans "l'ordre logique de la visite", car c'est à partir de cet ordre que l'on pourra déterminer où placer la l'aération.

Par facilité, j'ai créé une énumération représentant les quatre directions possibles me permettant d'indiquer la direction d'où vient le "point de passage précédant".

Puis j'ai créé la fonction retriveGalleries qui me permet de récupérer les "points de passage" dans l'ordre logique de la visite, et qui utilise cette notion de direction pour y arriver.

Cette fonction me renvoie un tableau d'indices qui correspondent à chaque fois à  une position ligne / colonne dans la grille à laquelle  se trouve un point de passage.

Une fois cette fonction créée, j'avais virtuellement déjà fini le travail, car, tout ce qu'il me restait à faire, c'était de provoquer l'affichage (sous forme de position ligne / colonne) de tous les Niemes indices de ce tableau (ou N correspond à la distance entre deux positions ventilées  ).

Allez, voici mon code

#include <iostream>
#include <vector>
struct Dimentions{
    size_t lines;
    size_t rows;
    size_t total;
};
enum Directions{
    left,
    right,
    up,
    down,
};
size_t toIndex(Dimentions const & dim, size_t line, size_t row){
    return line * dim.rows + row;
}
std::pair<size_t, size_t> fromIndex(size_t index,Dimentions const & dim){
    return std::make_pair<size_t, size_t>(index / dim.rows, index % dim.rows);
}
struct GroundMap{
public:
    GroundMap(size_t lines, size_t rows):dimentions{lines, rows, lines * rows}{
        datas.resize(dimentions.total);
    }
    Dimentions dimentions;
    std::vector<int> datas;
    size_t galleryCount = 0;
};
void loadMap(std::istream & ifs, GroundMap & map){
    for(int i = 0; i<map.dimentions.total; ++i){
        ifs>>map.datas[i];
        if(map.datas[i] == 0)
            ++map.galleryCount;
    }
}
void print(std::vector<size_t> const & trip, Dimentions const & dim, size_t distance){
    for(size_t i = distance;i<trip.size(); i+=distance+1){
        auto [line, row] = fromIndex(trip[i], dim);
        std::cout<< line<<" "<<row<<"\n";
    }
}
std::vector<size_t> retriveGalleries(GroundMap const & map){
    std::vector<size_t> result(map.galleryCount,0);
    auto rows = map.dimentions.rows;
    Directions nextDir = map.datas[1]== 0 ? right : down;
    for(size_t i = 1; i<result.size();++i){
        result[i] = ( nextDir == right? result[i-1] + 1 :
                         nextDir == down?  result[i-1] + rows :
                         nextDir == up?    result[i-1] - rows :
                                           result[i-1]-1);
        nextDir = result[i] - 1 != result[i-1] && map.datas[result[i]-1]==0 ? left  :
                  result[i] + 1 != result[i-1] && map.datas[result[i]+1]==0 ? right :
                  result[i] >= rows && result[i]-rows != result[i-1] &&  map.datas[result[i]-rows ]==0 ?up :
                  down;
    }
    return result;
}
int main(){
    size_t lines, rows, distance;
    std::cin>>lines>>rows>>distance;
    GroundMap map{lines, rows};
    loadMap(std::cin, map);
    auto trip  = retriveGalleries(map);
    print(trip, map.dimentions, distance);
}

PS: ne disposant pas de compte sur FranceIOI, et présumant en outre que ce problème n'est accessible que  si on en a résolut d'autres, quelqu'un pourrait il tester mon code et me dire s'il respecte les conditions de rapidités lors des tests?

rouIoude a écrit:

La moulinette ne prend pas le C++17

C++11 maxi

EDIT : J'ai modifié ta fonction print qui ne passait pas en C++11 comme si dessous :

void print(std::vector<size_t> const & trip, Dimentions const & dim, size_t distance){
    for(size_t i = distance;i<trip.size(); i+=distance+1){

        std::pair<size_t, size_t> plc = fromIndex(trip[i], dim);
        std::cout<< plc.first<<" "<<plc.second<<"\n";
    }
}

Mais il y a 4 tests en erreur sur 10 tests (dont le Test 2 dont on cause plus haut).

-
Edité par rouIoude 8 avril 2022 à 0:02:06

@koala01: j'aime bien ton idée ...
Mais tu as plusieurs fonctions. Cela ne va-t-il pas ralentir?

edit:
Si j'ai bien compris ton code ...
Tu as d'abord la grille de la galerie sous forme de "tableau" linéarisé à une dimension avec des indices.
Puis tu génères le tableau des points de passage en indice (pas en coordonnées)
Et tu parcours ce second tableau pour extraire les éléments à toutes les D positions et tu les affiches en coordonnées.
Tu as finalement deux tableaux dont la dimension est sans doute moins que le double du premier mais sûrement assez longue.
Je peux me demander si tu vas dépasser la limite de mémoire.
On ne m'a pas dit que mon code précédent dépassait le temps limite ni la mémoire limite.
J'ai décidé de converger vers ton idée.
J'ai remplacé le std::vector de int en bool. On va sauver sur l'espace et être plus cache-friendly.
Ce sera true si je peux passer, sinon ce sera false. Je met false sur la position que je viens de quitter.
J'ai gardé les indices pour valider si je suis out of range.
J'ai remplacé la fonction pour calculer l'indice par une macro.
J'ai corrigé mon bug pour D==0
-
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#define index(l,c) ((l)*C+(c))

bool valide(int l, int c, int L, int C) {
    return 0<=l && l<L && 0<=c && c<C;
}

int main(void) {
    // Je privilégie le bas et la droite même si toutes les directionss sont possibles.
    std::array<std::array<int, 2>, 4> directions = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}};
    std::vector<bool> galerie;
    int L, C, D;
    std::cin >> L >> C >> D;
    // Je favorise la dimension la plus grande, lignes vs colonnes
    if(C > L) {
        std::swap(directions[0], directions[1]);
        std::swap(directions[2], directions[3]);
    }
    galerie.resize(L*C);
    for(int l (0); l < L; l++) {
        for(int c (0); c < C; c++) {
            int intake;
            std::cin >> intake;
            galerie[index(l, c)] = intake == 0;
        }
    }
    int l = 0;
    int c = 0;
    int d = 1;
    if(D == 0) {
        d = 0;
       std::cout << l << " " << c << std::endl;
    }
    do {
        galerie[index(l, c)] = false;
        int il, ic;
        for(auto dir: directions) {
            il = dir[0];
            ic = dir[1];
            if(valide(l+il, c+ic, L, C) && galerie[index(l+il, c+ic)]) break;
        }
        l += il;
        c += ic;
        d++;
        if(d == D+1) {
            std::cout << l << " " << c << std::endl;
            d = 0;
        }
    } while(l != L-1 || c != C-1);
    return 0;
}

-
Edité par PierrotLeFou 8 avril 2022 à 6:49:09

PierrotLeFou a écrit:

@koala01: j'aime bien ton idée ...
Mais tu as plusieurs fonctions. Cela ne va-t-il pas ralentir?

A mon sens, beaucoup moins que le fait de dissiper les données en mémoire du fait d'un std::vector<std::vector&lt:size_t>>; même si on est à la limite entre une optimisation de la logique et une micro optimisation

PierrotLeFou a écrit:

J'ai remplacé le std::vector de int en bool. On va sauver sur l'espace et être plus cache-friendly.

PierrotLeFou a écrit:

J'ai remplacé la fonction pour calculer l'indice par une macro.

Ca, par contre, je peux être catégorique: la macro n'apporte rien, bien au contraire: elle nous fait renoncer au typage fort, et, bien que ce ne soit pas forcément un problème ici, il est toujours dommage de renoncer à une garantie en échange d'un gain tout à fait hypothétique de performances.

J'aurais, peut-être, pu déclarer la fonction inline pour forcer plus ou  moins le compilateur à l'inliner tout en ayant la garantie -- du fait de sa simplicité même -- qu'elle l'aurait été.

Il serait pas mal de faire un bench pour comparer, car tu n'as malgré tout peut être pas tors ;)  Mais si le gain (ou la perte) n'est pas suffisamment important(e) que pour être perceptible à l'utilisation, peut-être versons nous de nouveau dans la micro optimisation / l'optimisation prématurée?

Autant la linéarisation des donnée peut très facilement se justifier, ne serait-ce que par le fait que l'on évite grâce à elle de se retrouver avec une partie des données à gauche et l'autre partie à droite en ne nécessitant au final qu'une adaptation de la logique, autant je ne suis pas sur du tout de l'avantage réel que l'on a à passer d'un std::vector<size_t> à un std::vector<bool> ou d'utiliser une macro

Je n'ai pas accès plus que toi au site France IOI et générer une grille appropriée n'est pas tout à fait évident.
Quelque chose du genre à répéter?
.X...X...
...X...X.
xXXXXXXX.
...X...X.
.X...X...
C'est facile à générer à cause de la (ou les) simétrie.

Je peux générer facilement une grille 997 x 999 en Python.

Je pourrai tester macro vs fonction inline et int vs bool.

-
Edité par PierrotLeFou 8 avril 2022 à 8:23:21

Pour ma part je poursuis l'idée avec une fonction récursive.

Autant mon code trouve systématiquement le chemin de la galerie, autant je ne comprends pas pourquoi il décale presque à chaque fois l'emplacement du 1er aérateur. Les suivants sont correctement placés par rapport au 1er.

Pour le moment j'imprime la grille en sortie pour plus de clarté

#include <iostream>
#include <vector>
#include <utility>
#include <array>

using Grotte = std::vector<std::vector<int>>;

std::array<std::array<int, 2>, 4> direction
{
  0, 1,
  1, 0,
  0, -1,
  -1, 0
};
int compteur{0}, count{1};
std::vector<std::pair<int, int>> sortie;
//fonctions
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c);
bool dansPlateau(int lin, int col, int l, int c);

int main()
{
  std::ios::sync_with_stdio(false);
  int L{0}, C{0};
  std::cin >> L >> C >> compteur;
  Grotte lab;
  for (int l{0}; l < L; ++l)
  {
    for (int c{0}; c < C; ++c)
    {
      lab.push_back(std::vector<int>(C));
      std::cin >> lab [l][c];
    }
  }
  std::cout << "----------------------------------------\n";

  if (chemin(lab, 0, 0, 0, L, C))
  {
    for (int i{0}; i < L; i++)
    {
      for (int j{0}; j < C; j++)
      {
        if (lab [i][j] == 7)
        {
          std::cout << "\033[32m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
        else if (lab [i][j] == 5)
        {
          std::cout << "\033[31m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
        else
        {
          std::cout << "\033[38m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
      }
      std::cout << "\n";
    }
    for (int i{(int)sortie.size() - 1}; i >= 0; --i)
      std::cout << sortie [i].first << " " << sortie [i].second << '\n';
  }
  return 0;
}

bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c)
{
  if (x == l - 1 && y == c - 1)
    return true;

  int nx{0}, ny{0}, i{0};
  if (grille [x][y] == 0)
  {
    for (; i < 4; ++i)
    {
      if (i != (olddir + 2) % 4)
      {
        nx = x + direction [i][0];
        ny = y + direction [i][1];
      
        if (dansPlateau(nx, ny, l, c) && chemin(grille, nx, ny, i, l, c))
        {
          count++;

          if (count != compteur + 1)
            grille [nx][ny] = 5;
          else
          {
            count = 0;
            grille [nx][ny] = 7;
            sortie.push_back({nx, ny});
          }

          return true;
        }
      }
    }
  }
  return false;
}

bool dansPlateau(int lin, int col, int l, int c)
{
  return ((lin >= 0) && (lin < l) && (col >= 0) && (col < c));
}

Quelques exemples de grilles

4 4 3
0 0 1 1
1 0 1 1
1 0 0 0
1 1 1 0

sortie

2 1

3 6 1
0 0 1 0 0 0
1 0 0 0 1 0
1 1 1 1 1 0

sortie

0 1
1 2
0 3
0 5
2 5

4 5 3
0 0 1 1 1
1 0 0 0 0
1 1 1 1 0
1 1 1 1 0

sortie

1 2

3 4

9 11 7
0 1 1 0 0 0 1 1 1 1 1
0 0 0 0 1 0 1 0 0 0 0
1 1 1 1 1 0 1 0 1 1 0
1 1 0 0 0 0 1 0 0 1 0
1 1 0 1 1 1 1 1 0 1 0
1 1 0 1 1 1 1 0 0 1 0
1 1 0 0 0 0 1 0 1 0 0
1 1 1 1 1 0 1 0 1 0 1
1 1 1 1 1 0 0 0 1 0 0

sortie

0 5

5 2

8 7

2 7

5 10

-
Edité par Duncan4031 8 avril 2022 à 9:50:12

Bravo Pierrot, ton dernier code passe tous les tests !

En terme de vitesse, ils se valent tous, 0.22s pour les tests 9 et 10 sur la moulinette. (La moulinette donne les temps d'exécution)

Edit :

Duncan4031 a écrit:

autant je ne comprends pas pourquoi il décale presque à chaque fois l'emplacement du 1er aérateur. Les suivants sont correctement placés par rapport au 1er.

 C'est parce que tu démarres de la case 0,0 et que tu as donc D-1 espaces avec la suivante alors que les suivantes ont D espace entre deux conduits. 

-
Edité par rouIoude 8 avril 2022 à 9:46:59

si je change la ligne 37

if (chemin(lab, 0, 0, 0, L, C))

en

if (chemin(lab, 0, -1, 0, L, C))

la case 0,0 est prise en compte mais le résultat est faux

9 11 7
0 1 1 0 0 0 1 1 1 1 1
0 0 0 0 1 0 1 0 0 0 0
1 1 1 1 1 0 1 0 1 1 0
1 1 0 0 0 0 1 0 0 1 0
1 1 0 1 1 1 1 1 0 1 0
1 1 0 1 1 1 1 0 0 1 0
1 1 0 0 0 0 1 0 1 0 0
1 1 1 1 1 0 1 0 1 0 1
1 1 1 1 1 0 0 0 1 0 0
----------------------------------------
5 1 1 5 7 5 1 1 1 1 1 
5 5 5 5 1 5 1 5 5 5 5 
1 1 1 1 1 5 1 5 1 1 5 
1 1 5 5 5 5 1 7 5 1 5 
1 1 7 1 1 1 1 1 5 1 7 
1 1 5 1 1 1 1 5 5 1 5 
1 1 5 5 5 5 1 5 1 5 5 
1 1 1 1 1 5 1 5 1 5 1 
1 1 1 1 1 5 7 5 1 5 5 
0 4
4 2
8 6
3 7
4 10

qu'est ce qui m'échappe ? mystère pour le moment

Macro, fonction, ou fonction inline, ici il n'y aura aucune différence car tout est dans la même unité de traduction  et le compilateur inlinera tout. Le plus simple pour s'en convaincre: godbolt.

Pour ce qui est de la linéarisation, je ne pense pas qu'elle apporte beaucoup car elle consiste à transformer la grille 2D en séquence 1D de coordonnées qui ne servira qu'une fois. Sur les exo de france-ioi, En général, on nous pousse à préférer le mono-passe au multi-passes, où l'on traite les données au fil de l'eau. A penser comme une itération complexe avec visitation pour le traitement à l'intérieur.

PS: le récursif peut être problématique s'il n'est pas écrit pour être "terminal" comme c'est le cas ici: le compilateur va empiler les appel de fonctions, et sur les grandes dimensions comme france-ioi ne manquera pas de faire, la pile ne sera jamais assez grande.

Pour que la récursivité soit terminale, il faut soit que le chemin renvoie une valeur, soit le résultat inaltérée de la fonction appelée de façon récursive.

PPS: Entre temps, je me suis amusé, j'ai changé la fonction de test: pas besoin de tout vérifier. Et j'ai corrigé différemment le comptage pour tout uniformiser.

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>

[[noreturn]] void unreachable() { __builtin_unreachable(); }

#if 0
bool valide(int l, int c, int L, int C) {
    return 0<=l && l<L && 0<=c && c<C;
}
#endif

std::array<std::array<int, 2>, 4> directions {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};

struct Galerie {
    Galerie(std::size_t L_, std::size_t C_) : L(L_), C(C_), m_buffer(L*C) {}
    Galerie(std::size_t L_, std::size_t C_, std::istream &is) : Galerie(L_, C_) {
        for (std::size_t i=0; i < L*C && is >> m_buffer[i] ; ++i)
        { }
    }

    int const& operator()(std::size_t l, std::size_t c) const {
        return m_buffer[offset(l,c)];
    }
    int      & operator()(std::size_t l, std::size_t c)       {
        return m_buffer[offset(l,c)];
    }

    bool est_la_suite(int l, int c) const {
        return /*valide(l, c, L, C)
            &&*/ (*this)(l, c) == 0;
    }
private:
    std::size_t offset(std::size_t l, std::size_t c) const {
        assert(l < L);
        assert(c < C);
        return c + l * C;
    }

    std::size_t      L;
    std::size_t      C;
    std::vector<int> m_buffer;
};

int main() {
    std::size_t L, C, D;
    std::cin >> L >> C >> D;
    Galerie galerie(L, C, std::cin);

    std::size_t l = 0;
    std::size_t c = 0;
    std::size_t d = 0;
    while(l != L-1 || c != C-1)
    {
        galerie(l,c) = 2;

        if (d == D) {
            std::cout << l << " " << c << '\n';
            d = 0;
        } else {
            ++d;
        }
        
#if 0
        auto const wh = std::find_if(begin(directions), end(directions),
                [l,c,&galerie](auto const& p){ return galerie.est_la_suite(l+p[0], c+p[1]); });
        assert(wh != end(directions));
        auto const [il, ic] = *wh;
        l += il;
        c += ic;
#else
        auto find_next = [&](std::size_t & l, std::size_t & c) {
            if (l > 0   && galerie.est_la_suite(l-1, c)) return --l;
            if (l < L-1 && galerie.est_la_suite(l+1, c)) return ++l;
            if (c > 0   && galerie.est_la_suite(l, c-1)) return --c;
            if (c < C-1 && galerie.est_la_suite(l, c+1)) return ++c;
            unreachable();
            assert(!"should not happen");
        };
        find_next(l, c);
#endif
    }
    if(d == D) {
        std::cout << l << " " << c << '\n';
    }
    return 0;
}
// Vim: let $CXXFLAGS='-std=c++17 -Wall -Wextra'

Duncan4031 a écrit:

Pour ma part je poursuis l'idée avec une fonction récursive.

De manière générale, la récursivité est une technique particulièrement intéressante, seulement, lorsqu'elle est utilisée pour faire ce que l'on aurait pu faire avec une simple boucle, elle devient tout bonnement inutile

Déjà, parce que la technique est "compliquée" si on ne prend pas pour habitude de traiter en priorité le "cas de base" (le cas qui fera que  la fonction ne sera plus rappelée), mais aussi parce que mal utilisée, elle va avoir tendance à  saturer la pile d'appels, et à mener "très rapidement" le programme à planter pour cause de débordement.

Bien sur, la "figure de style" est intéressante, cependant, j'ai l'impression que cela rend le code inutilement complexe (qu'il te suffise de compter le nombre de blocs imbriqués pour t'en convaincre : tu en arrives à  fermer quatre blocs imbriqués pour renvoyer false), alors qu'il y a moyen de garder le code beaucoup plus simple.  Et la simplicité paye toujours, et souvent à différents points de vue, en programmation.

Ceci dit, peut être devrais tu simplement modifier un tout petit peu ta logique pour rendre le code plus "simple" (avec moins de blocs d'instructions imbriqués), en inversant le test if(grille[x][y]==0), car il est clair que, toute la logique qui suit ne peut renvoyer true que si c'est réellement le cas.

Dés lors, pourquoi ne modifierais tu  pas ta logique pour renvoyer false dés qu'il est clair que c'est ce qui doit être renvoyé, ce qui te permettrait de ne renvoyer true qu'une fois que tout ce qui doit être fait aurait été effectué ?

Cela donnerait un code proche de (copié collé avec inversion de quelques tests )

#include <iostream>
#include <vector>
#include <utility>
#include <array>
 
using Grotte = std::vector<std::vector<int>>;
 
std::array<std::array<int, 2>, 4> direction
{
  0, 1,
  1, 0,
  0, -1,
  -1, 0
};
int compteur{0}, count{1};
std::vector<std::pair<int, int>> sortie;
//fonctions
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c);
bool dansPlateau(int lin, int col, int l, int c);
 
int main()
{
  std::ios::sync_with_stdio(false);
  int L{0}, C{0};
  std::cin >> L >> C >> compteur;
  Grotte lab;
  for (int l{0}; l < L; ++l)
  {
    for (int c{0}; c < C; ++c)
    {
      lab.push_back(std::vector<int>(C));
      std::cin >> lab [l][c];
    }
  }
  std::cout << "----------------------------------------\n";
 
  if (chemin(lab, 0, 0, 0, L, C))
  {
    for (int i{0}; i < L; i++)
    {
      for (int j{0}; j < C; j++)
      {
        if (lab [i][j] == 7)
        {
          std::cout << "\033[32m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
        else if (lab [i][j] == 5)
        {
          std::cout << "\033[31m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
        else
        {
          std::cout << "\033[38m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
      }
      std::cout << "\n";
    }
    for (int i{(int)sortie.size() - 1}; i >= 0; --i)
      std::cout << sortie [i].first << " " << sortie [i].second << '\n';
  }
  return 0;
}
 
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c)
{
  if (x == l - 1 && y == c - 1)
    return true;
 
  int nx{0}, ny{0}, i{0};
  if (grille [x][y] != 0)
     return false;
  for (; i < 4; ++i)
  {
    if (i != (olddir + 2) % 4)
    {
      nx = x + direction [i][0];
      ny = y + direction [i][1];
      if(! dansPlateau(nx, ny, l, c)
          return false;
      if(! chemin(grille, nx, ny, i,l,c)
          return false;
      count++;
      grille [nx][ny] = 5;
      if (count == compteur + 1)
      {
        count = 0;
        grille [nx][ny] = 7;
        sortie.push_back({nx, ny});
      }
    }
  }
  return true;
}
 
bool dansPlateau(int lin, int col, int l, int c)
{
  return ((lin >= 0) && (lin < l) && (col >= 0) && (col < c));
}

Par contre, je trouve qu'il y a beaucoup trop de variables globales dans ton code, parce que les variables globales, C'EST MAL!!!

Enfin, une question quand même: pourquoi modifier tes valeurs d'entrées?

J'ai bien conscience que c'est rendu nécessaire par la récursivité, afin de pouvoir trouver les points déjà observés, mais ... que va-t-il se passer si on doit faire "autre chose" après avoir placé l'aération?

@koala01

je comprends bien que trouver une solution en récursif est plus complexe.

ici je suis dans un exercice et pour continuer mon expérience en codage, je voulais voir en récursif ce que cela fait et des difficultés qu'on rencontre.

je vais voir avec ton idée

Edit: tester à chaud le programme ne donne jamais de réponse.

-
Edité par Duncan4031 8 avril 2022 à 15:56:41

int explore(Grille & grille, int l, int c, int count, int C) {
    grille(l, c) = 2;
    if (C +/-1 ? == count) { cout << .... ; count = 0; }
    else ++ count;
    if (grille.est_sortie(l, c)) return count;
    find_next(grille, l, c); // cf mes réponses précédentes ; à la sortie l (X)ou c a changé
    return explore(grille, l, c, count, C);
}

coté expression récursive -- ce qui est très proche de l'expression itérative.

NB: renvoyer le compteur n'apporte pas grand chose. Peut-etre avoir un vecteur des résultats que l'on empile au fur et à mesure à la place du cout.

-
Edité par lmghs 8 avril 2022 à 15:56:14

Finalement j'ai revu mon programme pour que la recherche démarre à partir de la fin de la grille.

Et yes je passe tous les tests.

Un peu surpris en terme de rapidité

En prenant les tests 9 et 10 de France IOI

le programme de Pierrot donne 0,22 et 0,22s

celui de lmghs donne 0,21 et 0,21s

et le mien 0,22 et 0,23s

J'étais persuadé qu'en récursif mon prog se traînerait.

#include <iostream>
#include <vector>
#include <utility>
#include <array>
using Grotte = std::vector<std::vector<int>>;
std::array<std::array<int, 2>, 4> direction
{
  0, -1,
  -1, 0,
  0, 1,
  1, 0
};
int compteur{0}, tmp{0};
std::vector<std::pair<int, int>> sortie;
//Fonctions
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c);
bool dansPlateau(int lin, int col, int l, int c);
int main()
{
  std::ios::sync_with_stdio(false);
  int L{0}, C{0};
  std::cin >> L >> C >> compteur;
  Grotte lab;
  for (int i{0}; i < L; ++i)
  {
    lab.push_back(std::vector<int>(C));
    for (int j{0}; j < C; ++j)
    {
      std::cin >> lab [i][j];
    }
  }
  std::cout << "----------------------------------------\n";
  if (chemin(lab, L - 1, C, 0, L, C))
  {
    for (int i{0}; i < L; i++)
    {
      for (int j{0}; j < C; j++)
      {
        if (lab [i][j] == 7)
        {
          std::cout << "\033[32m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
        else if (lab [i][j] == 5)
        {
          std::cout << "\033[31m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
        else
        {
          std::cout << "\033[38m" << lab [i][j] << " ";
          std::cout << "\033[0m";
        }
      }
      std::cout << "\n";
    }
    for (int i{0}; i < (int)sortie.size(); ++i)
      std::cout << sortie [i].first << " " << sortie [i].second << '\n';
  }
  return 0;
}
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c)
{
  int nx{0}, ny{0}, i{0};
  if (x == 0 && y == 0)
    return true;
  if (grille [x][y] == 0 || y == c)
  {
    for (; i < 4; ++i)
    {
      if (i != (olddir + 2) % 4)
      {
        nx = x + direction [i][0];
        ny = y + direction [i][1];

        if (dansPlateau(nx, ny, l, c) && chemin(grille, nx, ny, i, l, c))
        {
          tmp++;
          if (tmp == compteur + 1)
          {
            tmp = 0;
            grille [nx][ny] = 7;
            sortie.push_back({nx, ny});
          }
          else
            grille [nx][ny] = 5;
          
          return true;
        }
      }
    }
  }
  return false;
}
bool dansPlateau(int lin, int col, int l, int c)
{
  return ((lin >= 0) && (lin < l) && (col >= 0) && (col < c));
}

Merci à tous pour vos interventions, 

C'est toujours très enrichissant d'échanger.

une question à @lmghs

je ne comprends pas la ligne

[[noreturn]] void unreachable() { __builtin_unreachable(); }

Si tu pouvais m'expliquer ce qu'elle fait

Edit : une remarque le fait d'ajouter la ligne

std::ios::sync_with_stdio(false);

fait gagner dans cet exercice à chaque programme 0,3s

-
Edité par Duncan4031 8 avril 2022 à 17:03:29

Vu les écarts vus, je dirai qu'il n'y en a pas vraiment et que toutes les solutions se valent à ce niveau.

Et je maintiens, que quand il y a des "limites" de perfs, ça ne se joue pas à si peu.

Pour le unreachable, c'était pour assumer qu'il n'est pas censé avoir de cas hors des 4 possibles ifs. C'est pour contourner l'oubli de return. C'est dégueulasse. Juste une exploration personnelle. Ne le retient pas.

-
Edité par PierrotLeFou 8 avril 2022 à 17:34:20