Partage
  • Partager sur Facebook
  • Partager sur Twitter

Baguenaudier

Baguenaudier france-ioi

Sujet résolu
    7 novembre 2021 à 20:33:04

    Bonjour tout le monde, je ne comprends pas cet exercice, que dois-je faire ? (si vous voulez le lien du problème, le voici : http://www.france-ioi.org/algo/task.php?idChapter=671&iOrder=2)

    Merci d'avance pour vos réponses

    Vous avez découvert un nouveau jeu très amusant. Celui-ci se joue sur un plateau de N cases alignées numérotées de 1 à N sur lesquelles on peut poser des jetons.

    • À tout moment, chaque case contient au plus un jeton.
    • Une case contenant un jeton est dite remplie, une case n'en contenant aucun est dite vide.
    • Au début de la partie, toutes les cases sont remplies.

    Les règles du jeu sont les suivantes :

    • À tout moment on peut vider ou remplir la case 1.
    • Si la case 1 est remplie, alors on peut remplir ou vider la case 2. (Règle valable pour N >= 2)
    • Pour tout 3 <= K <= N, on peut remplir ou vider la case K lorsque les K - 2 premières cases sont vides et que la case K - 1 est remplie. (Règle valable pour N >= 3)

    Le but du jeu est de vider toutes les cases. Vous avez décidé d'écrire un programme permettant de résoudre le jeu en un minimum de coups.

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

    • Temps : 0,5 s sur une machine à 1 GHz.
    • Mémoire : 4 000 ko.

    Contraintes

    • 1 <= N <= 18, où N est le nombre de cases du plateau.

    Entrée

    L'entrée est composée d'un unique entier : N, le nombre de cases du plateau.

    Sortie

    Votre programme doit afficher P lignes, avec P le nombre minimal de coups nécessaire pour finir le jeu.

    Chacune des P lignes doit contenir un entier Pi compris entre 1 et N, décrivant le ie coup de votre séquence, par l'indice de la case remplie ou vidée à ce coup.

    Exemple

    entrée :

    4

    sortie :

    2
    1
    4
    1
    2
    1
    3
    1
    2
    1

    Commentaires

    Il s'agit ici de résoudre le jeu pour N = 4. Il faut au minimum 10 coups pour résoudre le jeu.

    -
    Edité par Nonoze 7 novembre 2021 à 20:34:38

    • Partager sur Facebook
    • Partager sur Twitter

    Le C++, c'est beaucoup trop bien (et addictif)

      8 novembre 2021 à 11:10:58

      Bonjour,

      la première étape est de trouver un algo qui va te permettre de résoudre le problème. Il n'y a pas 36 manières de faire : essaye avec de petites instances et tu verras bien où ça te mène :)

      Par exemple pour N=1 c'est simple : tu vides la case 1 est c'est bon …

      N=2 : tu vides la case 2 pour tomber sur le cas N=1 …

      N=3 : tu vides la case 1, tu vides la case 3, tu remplis 1 , tu vides 2 et tu vides 1 …

      • Partager sur Facebook
      • Partager sur Twitter
        8 novembre 2021 à 15:24:27

        Mais je n'ai pas compris ce qu'il faut faire (vider et remplir)
        • Partager sur Facebook
        • Partager sur Twitter

        Le C++, c'est beaucoup trop bien (et addictif)

          8 novembre 2021 à 15:32:33

          On peut supposer qu'une case remplie vaut 1 et une case vide vaut 0.
          Je pense que ça se fait de façon récursive. bien que je me sois déjà gouré là-dessus ...

          edit:

          Pour N > 2, je pense qu'on peut déduire la façon optimale pour N+1 si on la connait pour N.

          -
          Edité par PierrotLeFou 8 novembre 2021 à 15:41:13

          • Partager sur Facebook
          • Partager sur Twitter

          Le Tout est souvent plus grand que la somme de ses parties.

            8 novembre 2021 à 15:45:05

            Oui, d'accord mais je n'ai pas compris l'énoncé, pourrais-tu mieux m'expliquer

            merci d'avance

            • Partager sur Facebook
            • Partager sur Twitter

            Le C++, c'est beaucoup trop bien (et addictif)

              8 novembre 2021 à 15:54:54

              Qu'est-ce que vous n'avez pas compris dans l'énoncé ?
              • Partager sur Facebook
              • Partager sur Twitter
              Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
                8 novembre 2021 à 15:57:48

                Je ne comprends pas ce qu'il faut faire (que valent les nombres qu'on doit resortir ?)

                -
                Edité par Nonoze 8 novembre 2021 à 16:04:14

                • Partager sur Facebook
                • Partager sur Twitter

                Le C++, c'est beaucoup trop bien (et addictif)

                  8 novembre 2021 à 16:41:36

                  Il faut trouver la séquence de mouvement (vider ou remplier une des K cases) pour qu'à la fin il n'y ait que des cases vides, en respectant les contraintes à chaque étape.

                  • Partager sur Facebook
                  • Partager sur Twitter
                  Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
                    8 novembre 2021 à 16:55:12

                    Ah ok, j'ai compris, merci

                    Je vais appliquer les conseil de White Crow et de PierrotLeFou

                    .

                    .

                    .

                    Edit:

                    Jai essayé pendant hyper longtemps, et finalement, j'ai réussis.

                    Merci pour toutes ces indications

                    -
                    Edité par Nonoze 9 novembre 2021 à 20:38:48

                    • Partager sur Facebook
                    • Partager sur Twitter

                    Le C++, c'est beaucoup trop bien (et addictif)

                    Baguenaudier

                    × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                    • Editeur
                    • Markdown