Partage
  • Partager sur Facebook
  • Partager sur Twitter

Boîtes factorielles

Boîtes factorielles France-ioi

Sujet résolu
    7 novembre 2021 à 11:38:07

    Bonjour, je n'arrive pas à optimiser plus que cela mon code, car il est bon mais il n'est pas assez rapide pour les 2 derniers test, merci d'avance

    Un marchand de légumes très maniaque souhaite ranger ses petits pois en les regroupant en boîtes de telle sorte que chaque boîte contienne un nombre factoriel de petits pois. On rappelle qu'un nombre est factoriel s'il est de la forme 1, 1 x 2, 1 x 2 x 3, 1 x 2 x 3 x 4... et qu'on les note sous la forme suivante :

    n!=1×2×3××(n1)×nn!=1×2×3×…×(n−1)×n

    Il souhaite également utiliser le plus petit nombre de boîtes possible.

    Ainsi, s'il a 17 petits pois, il utilisera :

    • 2 boîtes de 3! = 6 petits pois
    • 2 boîtes de 2! = 2 petits pois
    • 1 boîte de 1! = 1 petits pois
    ce qui donne bien 2 x 3! + 2 x 2! + 1 x 1! = 12 + 4 + 1 = 17.

    D'une manière générale, s'il a nbPetitsPois, il doit trouver une suite a1,a2,,apa1,a2,…,ap d'entiers positifs ou nuls avec ap>0ap>0 et telle que :

    nbPetitsPois=a1×1!+a2×2!++ap×p!nbPetitsPois=a1×1!+a2×2!+…+ap×p!
    avec a1++apa1+…+ap minimal.

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

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

    Contraintes

    1<= nbPetitsPois <= 500 000 000

    Entrée

    Un unique entier, nbPetitsPois le nombre total de petits poids.

    Sortie

    • Sur le première ligne, l'entier p
    • Sur la seconde ligne, les entiers a1,a2,,apa1,a2,…,ap

    Exemple

    entrée :

    17

    sortie :

    3
    1 2 2
    #include <iostream>
    using namespace std;
    
    int main()
    {
    	int nbPetitsPois; cin >> nbPetitsPois;
    	int NbrFactoriels[14] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800};
    	int comp = 0, res[14] = {0};
    	int i = 1;
    	int var = nbPetitsPois;
    	while(comp<nbPetitsPois)
    	{
    		if (var>=NbrFactoriels[i] && var<NbrFactoriels[i+1])
    		{
    			res[i]++;
    			comp+=NbrFactoriels[i];
    			var = nbPetitsPois-comp;
    			i = 0;
    		}
    		i++;
    	}
    	int max;
    	for (int i = 14; i > 0; --i)
    	{
    		if (res[i] != 0)
    		{
    			cout << i << "\n";
    			max = i;
    			break;
    		}
    	}
    	for (int i = 1; i <= max; ++i)
    	{
    		cout << res[i] << " ";
    	}
    	return 0;
    }

    -
    Edité par Nonoze 7 novembre 2021 à 11:40:18

    • Partager sur Facebook
    • Partager sur Twitter

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

      7 novembre 2021 à 13:55:29

      Nonoze a écrit:

      Bonjour, je n'arrive pas à optimiser plus que cela mon code, car il est bon mais il n'est pas assez rapide pour les 2 derniers test, merci d'avance


      Ta boucle while est maladroite :

      • tu réinitialises i à 0  (et tu repars vraiment à zéro) 
      • tu retires factorielle par factorielle donc si le quotient est grand, tu vas trop boucler.

      L'algo qui marche ici est l'algo glouton : divise à chaque fois par la plus grande factorielle et recommence avec le reste, tu passeras tous les tests.

      -
      Edité par PascalOrtiz 7 novembre 2021 à 14:19:42

      • Partager sur Facebook
      • Partager sur Twitter
        7 novembre 2021 à 18:17:00

        PascalOrtiz a écrit:

        Ta boucle while est maladroite :

        • tu réinitialises i à 0  (et tu repars vraiment à zéro) 
        • tu retires factorielle par factorielle donc si le quotient est grand, tu vas trop boucler.

        L'algo qui marche ici est l'algo glouton : divise à chaque fois par la plus grande factorielle et recommence avec le reste, tu passeras tous les tests.

        Ok PascalOrtiz, merci de ta réponse, mais je ne comprends pas le :

        "divise à chaque fois par la plus grande factorielle et recommence avec le reste"

        Il faut faire quoi concrètement ?


        Ps: (merci de prendre du temps pour m'aider sur ce problème, ça fait super plaisir ;))





        Ok, merci PascalOrtiz, j'ai réussis (j'ai juste modifier mon int i = 0, je l'ai remplacer par int i = 13 et i--)

        Merci beaucoup

        -
        Edité par Nonoze 7 novembre 2021 à 20:30:21

        • Partager sur Facebook
        • Partager sur Twitter

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

          7 novembre 2021 à 23:04:06

          Effectivement ce nouveau code passe les tests mais ta boucle while reste vraiment non optimale :

          • ton i n'arrête pas de faire des allers et retours pour rien 
          • tu répètes une opération qui pourrait se faire en une fois. 

          Si on affiche sur cout le flux d'exécution de ton code (voir plus bas), on voit bien qu'il n'est pas optimal :

          #include <iostream>
          using namespace std;
           
          int main()
          {
              long int  nbPetitsPois=4*720+3*24;
              long int NbrFactoriels[14] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800};
              int comp = 0, res[14] = {0};
              int i = 13;
              int var = nbPetitsPois;
              while(comp<nbPetitsPois)
              {
                  if (var>=NbrFactoriels[i] && var<NbrFactoriels[i+1])
                  {
                      res[i]++;
                      comp+=NbrFactoriels[i];
                      var = nbPetitsPois-comp;
                      cout << "if "<< i << "\n";
                      i = 13;
          
                  }
                  i--;
                      cout << "while "<< i << "\n";        
              }
              int max;
              for (int i = 13; i > 0; --i)
              {
                  if (res[i] != 0)
                  {
                      cout << i << "\n";
                      max = i;
                      break;
                  }
              }
              for (int i = 1; i <= max; ++i)
              {
                  cout << res[i] << " ";
              }
              return 0;
          } 
          



          Tu vois que j'ai choisis pour nbPetitsPois=4*6!+3*4! (je note k! factorielle de k)

          Pas la peine de répéter le retrait de 6! à nbPetitsPois mais autant calculer son quotient par 6! (tu vas trouver 4) et recommencer l'opération avec la factorielle plus petite suivante sur le reste de la division. Le nouveau quotient sera 3 et le reste nul donc le compte sera bon.

          Voici les affichages lus :

          while 12
          while 11
          while 10
          while 9
          while 8
          while 7
          while 6
          if 6
          while 12
          while 11
          while 10
          while 9
          while 8
          while 7
          while 6
          if 6
          while 12
          while 11
          while 10
          while 9
          while 8
          while 7
          while 6
          if 6
          while 12
          while 11
          while 10
          while 9
          while 8
          while 7
          while 6
          if 6
          while 12
          while 11
          while 10
          while 9
          while 8
          while 7
          while 6
          while 5
          while 4
          if 4
          while 12
          while 11
          while 10
          while 9
          while 8
          while 7
          while 6
          while 5
          while 4
          if 4
          while 12
          while 11
          while 10
          while 9
          while 8
          while 7
          while 6
          while 5
          while 4
          if 4
          while 12
          6
          0 0 0 3 0 4 

          Bien sûr, ton code passe les tests parce que les quotients sont petits donc on peut se permettre de répéter.

          -
          Edité par PascalOrtiz 7 novembre 2021 à 23:10:23

          • Partager sur Facebook
          • Partager sur Twitter
            8 novembre 2021 à 7:46:25

            Alors, mais moi je n'ai pas fait i = 13 (pour le 2eme), j'ai fait i++;

            regarde mon code :

            #include <iostream>
            using namespace std;
            
            int main()
            {
            	int nbPetitsPois; cin >> nbPetitsPois;
            	int long long NbrFactoriels[14] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800};
            	int comp = 0, res[14] = {0};
            	int i = 13;
            	int var = nbPetitsPois;
            	while(comp<nbPetitsPois)
            	{
            		if (var>=NbrFactoriels[i] && var<NbrFactoriels[i+1])
            		{
            			res[i]++;
            			comp+=NbrFactoriels[i];
            			var = nbPetitsPois-comp;
            			i++;
            		}
            		i--;
            	}
            	int max;
            	for (int i = 13; i > 0; --i)
            	{
            		if (res[i] != 0)
            		{
            			cout << i << "\n";
            			max = i;
            			break;
            		}
            	}
            	for (int i = 1; i <= max; ++i)
            		cout << res[i] << " ";
            	return 0;
            }



            -
            Edité par Nonoze 8 novembre 2021 à 7:47:34

            • Partager sur Facebook
            • Partager sur Twitter

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

              8 novembre 2021 à 11:45:10

              Nonoze a écrit:

              Alors, mais moi je n'ai pas fait i = 13 (pour le 2eme), j'ai fait i++;

              regarde mon code :

              #include <iostream>
              using namespace std;
              
              int main()
              {
              	int nbPetitsPois; cin >> nbPetitsPois;
              	int long long NbrFactoriels[14] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800};
              	int comp = 0, res[14] = {0};
              	int i = 13;
              	int var = nbPetitsPois;
              	while(comp<nbPetitsPois)
              	{
              		if (var>=NbrFactoriels[i] && var<NbrFactoriels[i+1])
              		{
              			res[i]++;
              			comp+=NbrFactoriels[i];
              			var = nbPetitsPois-comp;
              			i++;
              		}
              		i--;
              	}
              	int max;
              	for (int i = 13; i > 0; --i)
              	{
              		if (res[i] != 0)
              		{
              			cout << i << "\n";
              			max = i;
              			break;
              		}
              	}
              	for (int i = 1; i <= max; ++i)
              		cout << res[i] << " ";
              	return 0;
              }



              -
              Edité par Nonoze il y a environ 1 heure


              D'accord donc cette fois ton i décroit normalement mais il reste le problème (mineur) de répéter le retrait plutôt que de prendre le quotient. Donc j'aurais plutôt écrit :

              #include <iostream>
              #include <vector>
              using namespace std;
              
              int main() {
                long long nbPetitsPois;
                long long NbrFactoriels[] = {1,       1,        2,         6,         24,
                                             120,     720,      5040,      40320,     362880,
                                             3628800, 39916800, 479001600, 6227020800};
                vector<int> coeffs{};
                size_t i = 13;
                cin >> nbPetitsPois;
                while (NbrFactoriels[i] > nbPetitsPois)
                  i--;
                cout << i << endl;
              
                while (nbPetitsPois > 0) {
                  lldiv_t qr = div(nbPetitsPois, NbrFactoriels[i]);
                  coeffs.push_back(qr.quot);
                  nbPetitsPois = qr.rem;
                  i--;
                }
              
                for (size_t j = 0; j < i; j++)
                  cout << 0 << " ";
              
                for (size_t j = 0; j < coeffs.size(); j++)
                  cout << coeffs[coeffs.size() - j - 1] << " ";
              
                cout << endl;
              
                return 0;
              }
              

              div sert juste à récupérer en une seule opération le quotient et le reste.

              • Partager sur Facebook
              • Partager sur Twitter
                8 novembre 2021 à 15:25:52

                Hein oui, ton code est logique !

                Mais comme ils marchent tous les deux, c'est bon

                • Partager sur Facebook
                • Partager sur Twitter

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

                Boîtes factorielles

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