Partage
  • Partager sur Facebook
  • Partager sur Twitter

france ioi utulisation trop important de la memoir

nombreux prouduits

    22 août 2021 à 19:05:12

    je suis actuellment sur ce sujet
    "

    Agréablement surpris par l'efficacité de son système de distributeurs, Gérard a décidé de le généraliser à tous les produits alimentaires de son magasin. Il vous demande donc de gérer maintenant l'ensemble de ses distributeurs dans un même programme.

    À chaque type de produit est associé un numéro d'identification. C'est également par ce numéro qu'on identifie chaque distributeur.

    "
    INPUT

    La première ligne de l'entrée contient un entier : nbDistributeurs.

    La deuxième ligne contient un entier : nbOpérations.

    Chacune des nbOpérations lignes suivantes contient trois entiers séparés par des espaces, et représente une opération. Celles-ci sont données dans l'ordre où les opérations sont effectuées. Les trois entiers sont respectivement :

    1. le numéro du distributeur sur lequel porte l'opération ;
    2. la quantité de produits concernés par l'opération. Cette quantité est un entier positif lorsqu'il s'agit d'un achat par Gérard (ajout) et négatif lorsqu'il s'agit d'une vente (retrait) ;
    3. 0 si l'opération est une vente. S'il s'agit d'un achat, cet entier représente la date de péremption du produit, sous la forme aaaammjj (année, mois, jour).

    OUTPUT

    Vous devez afficher nbDistributeurs lignes sur la sortie, qui représentent les distributeurs, dans l'ordre de leur code d'identification. Chaque ligne contient un entier : la date de péremption la plus petite parmi les produits restants dans le distributeur, au même format que dans l'entrée.

    Si une file est vide, vous devez afficher 0 à la place de la date.

    EXAMPLE

    input

    1
    8
    1 3 20040810
    1 -1 0
    1 -1 0
    1 3 20040920
    1 -1 0
    1 4 20040916
    1 -3 0
    1 -2 0

     OUTPUT

    20040916

     mon code utulise pluseiur espace dans la memoire

    comment je peut ameliorer mon code

    #include<bits/stdc++.h>
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int nbDist, nbOper;
        cin>>nbDist>>nbOper;
        queue<int>arr[nbDist];
        for(int i = 0; i < nbOper; i++) {
            int id, nb, date;
            cin>>id>>nb>>date;
            if(id > 0) {
                if(nb > 0) {
                    for(int i = 0; i < nb; i++)
                        arr[id - 1].push(date);
                }else {
                    while(nb < 0 && !arr[id - 1].empty()) {
                        nb++;
                        arr[id - 1].pop();
                    }
                }
            }
        }
        for(int i = 0; i < nbDist; i++) {
            if(arr[i].empty()) cout<<"0\n";
            else {
                int min = arr[i].front();
                arr[i].pop();
                while(!arr[i].empty()) {
                    if(min > arr[i].front()) min = arr[i].front();
                    arr[i].pop();
                }
                cout<<min<<"\n";
            }
        }
    }

    et merci



    • Partager sur Facebook
    • Partager sur Twitter
      25 août 2021 à 17:47:33

      Il semble qu'on t'a oublié ...
      L'énoncé n'est pas clair. Est-ce que les numéros de distributeur sont forcément entre 0 (ou 1) et nbDistributeurs?
      Ton code semble le croire.
      > Vous devez afficher nbDistributeurs lignes sur la sortie, qui représentent les distributeurs, dans l'ordre de leur code d'identification
      Est-ce qu'on doit trier les entrées ou si elles seront déjà triées?
      Je le ferais avec un vector>array<int, 2>>
      Pour chaque distributeur, je garderais le nombre de produits restants et la date de péremption la moins éloignée.
      Si c'est un achat, tu modifies le nombre et tu vérifie la date et la change au besoin.
      Si c'est une vente, tu ne modifies que le nombre de produits (je suppose que France IOI est honnète et qu'on ne tombera pas en back order ...)
      Si le nombre de produits à la fin est 0, j'affiche 0.
      Sinon, j'affiche la date conservée.
      • Partager sur Facebook
      • Partager sur Twitter

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

        26 août 2021 à 14:09:40

        Bonjour,

        En effet, l'énoncé ne semble pas indiquer que les livraisons de produits se font par ordre croissant de date. Ton code le présuppose car les articles sont ôtés en supposant que les premiers sont les plus anciens, mais ne le suppose plus pour fournir le résultat.
        Le nombre max d'articles livrés ne semble pas indiqué. Si tu reçois un milliard d'articles ton code va empiler un milliard d'objets, c'est peut-être ça qui provoque l'utilisation trop grande de la mémoire.
        Empiler pour chaque livraison, un couple (quantité,date) qui serait trié gère les 2 cas précédents.

        Comme l'a aussi souligné PierrotLeFou, rien ne semble indiquer l'intervalle où seraient les id de distributeurs. Pour gérer ce cas, il faudrait alors gérer dynamiquement tous les id de distributeurs; et trier par leur identifiant avant de retourner le résultat. Mais alors si un distributeur n'a jamais été cité, on n'aurait pas son id, et on ne saurait pas où le positionner dans la liste de résultat. Ça n'aurait pas de sens.
        Si on lit l'exemple, on peut peut-être supposer que les numéros de distributeurs sont bien des nombres entre 1 et nbDistributeurs inclus. C'est ce que j'utiliserais sans plus d'infos.

        Comme amélioration, je te propose un exemple de possible solution où tu pourras, je l'espère, t'y retrouver.

        #include <iostream>
        #include <vector>
        #include <deque>
        #include <algorithm>
        #include <string>
        
        using  Date = std::string;
        
        struct Article {
        	int   qte;
        	Date  date;
        };
        
        class Pool {
        public:
        	// enlève nb articles parmi les plus anciens
        	// retourne 0 ou l'opposé du nombre d'articles manquants
        	int  pop( int nb ) {
        		while ( nb > 0 ) {
        			if ( data.empty() )
        				return  -nb;             // pas assez d'articles
        			if ( nb < data.front().qte ) {
        				data.front().qte -= nb;  // ôter du plus ancien
        				nb = 0;
        			}
        			else {
        				nb -= data.front().qte;
        				data.pop_front();        // supprimer le plus ancien
        			}
        		}
        		return  0;
        	}
        
        	// ajoute nb articles de date date
        	void  push( int nb, Date date ) {
        		Article  article{nb, date};
        
        		auto it = std::lower_bound(     // trouver si existe et sinon où insérer dans vecteur trié
        				data.begin(),
        				data.end(),
        				article,
        				[](Article const&l,Article const&r){return l.date<r.date;}  // triés par date
        			);
        		if ( it != data.end()  &&  it->date == date ) {
        			it->qte += nb;              // existait à cette date : augmenter la qté associée
        		}
        		else {
        			data.insert( it, article ); // n'existait pas : nouvelle entrée insérée à sa position
        		}
        	}
        
        	bool  empty()const {
        		return  data.empty();
        	}
        
        	Date  date_of_oldest()const {
        		return  data.front().date;
        	}
        
        private:
        	std::deque<Article>  data;  // invariant: articles triés par date croissantes
        };
        
        
        int  main() {
        	std::ios::sync_with_stdio( false );
        	std::cin.tie( 0 );
        	int  nbDist, nbOper;
        
        	std::cin >> nbDist >> nbOper;
        
        	std::vector<Pool>  distributeurs( nbDist );  // les données de chaque distributeur
        
        	for ( int i = 0 ; i < nbOper ; ++i ) {
        		int  id, nb;
        		Date  date;
        		std::cin >> id >> nb >> date;
        		if ( id > 0 ) {
        			if ( nb > 0 ) {
        				distributeurs[id-1].push( nb, date );
        			}
        			else {
        				(void)distributeurs[id-1].pop( nb );
        			}
        		}
        	}
        	for ( auto const&  art  :  distributeurs ) {
        		if ( art.empty() ) {
        			std::cout << "0\n";
        		}
        		else {
        			std::cout << art.date_of_oldest() << '\n';
        		}
        	}
        }

        La date, elle, est indiqué avec le format aaaammjj donc un article de Noël de l'an 800 devrait être indiqué "08001225" (il semblerait qu'un distributeur vend la couronne de Charlemagne :lol:) . Ton code ne respecte pas cette contrainte, c'est pourquoi j'utilise std::string au lieu de int.

        • Partager sur Facebook
        • Partager sur Twitter

        En recherche d'emploi.

          26 août 2021 à 14:42:42

          Après réflexion, je doute que France IOI exige quelque chose de compliqué.
          Ce qui me surprend dans le résultat est qu'ils donnent 20040916, alors que logiquement on devrait avoir 20040810
          Le nombre de produits ne passe même pas à 0 avant le nouvel arrivage.
          Je donne mon code en fonction de mes hypothèses. Notez que je ne peux pas colorer mon code à cause de ma synthèse vocale.
          (on peut faire un copier-coller pour retrouver l'indentation)
          -
          #include <iostream>
          #include <vector>
          #include <array>
          #define PRODUIT 0
          #define DATE 1
          int main(void) {
              int nbDistributeurs;
              std::cin >> nbDistributeurs;
              std::vector<std::array<int, 2>> lesDistributeurs;
              std::array<int, 2> operation = { 0 };
              for(int i = 0; i < nbDistributeurs; i++)
                  lesDistributeurs.push_back(operation);
              int nbOperations;
              std::cin >> nbOperations;
              for(int i = 0; i < nbOperations; i++) {
                  int idDistributeur, nbProduits, datePeremption;
                  std::cin >> idDistributeur >> nbProduits >> datePeremption;
                  lesDistributeurs[idDistributeur-1][PRODUIT] += nbProduits;
                  if(nbProduits > 0) {
                      if(lesDistributeurs[idDistributeur-1][DATE] == 0 || datePeremption < lesDistributeurs[idDistributeur-1][DATE])
                          lesDistributeurs[idDistributeur-1][DATE] = datePeremption;
                  } else {   // je suppose qu'on a toujours nbProduits != 0
                      if(lesDistributeurs[idDistributeur-1][PRODUIT] == 0)
                          lesDistributeurs[idDistributeur-1][DATE] = 0;
                  }
              }
              for(int i = 0; i < nbDistributeurs; i++) {
                  if(lesDistributeurs[i][PRODUIT])
                      std::cout << lesDistributeurs[i][DATE] << std::endl;
                  else
                      std::cout << 0 << std::endl;
              }
              return 0;
          }
          • Partager sur Facebook
          • Partager sur Twitter

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

            26 août 2021 à 19:56:48

            Salut,  sinon ce que tu peux faire c'est mettre chacune des lignes de ton input dans une structure de donnees comme

            typedef struct Achat {unsigned int nbProducts : 10;}Achat;
            typedef struct Vente {unsigned int hash_date : 10;}Vente;//on utilise map<int, int> pour reduire la taille de la date
            
            typedef struct tp {
                    unsigned int distrib : 15;
                    union S{Achat achat;//ici c'est
                            Vente vt;
                    };
            }tp;

            Une fois que tu as remplit par exemple ton

            vector<tp>input(nbOper);

            Tu peux traiter tout les distributeurs dans une file chacun séparement (et pas tous les avoir dans ton arr)

            Normalement tu utilise moins de place.

            Aussi les contraintes sur le site IOI :

            • 0 <= nbProduits <= 1 000, où nbProduits est le nombre de produits d'un distributeur à un moment donné.
            • 1 <= nbDistributeurs <= 20 000, où nbDistributeurs est le nombre de distributeurs du magasin.
            • 1 <= iDistributeur <= nbDistributeurs, où iDistributeur est le code d'identification d'un distributeur.
            • 1 <= nbOpérations <= 300 000, où nbOpérations est le nombre d'opérations (achats ou ventes) à traiter.
            • 0 <= année < 10 000, où année est l'année d'une date de péremption.





            • Partager sur Facebook
            • Partager sur Twitter
              27 août 2021 à 2:15:04

              @Cencoremoi:
              Est-ce que ma façon de traiter le problème était correcte ou pas?
              Ce qui prenait le plus de place à mon avis est le fait que les 300000 opérations étaient gardées en mémoire.
              Ce que je ne fais pas.
              Le nombre de produits a peu ou pas d'impact.
              • Partager sur Facebook
              • Partager sur Twitter

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

                27 août 2021 à 9:07:23

                @pierroLeFou si je dis pas de betises, quand tu enleve tes elements de ton tableau tu le fais sans regarder l'ordre dans lequel ils ont étés mis dans la file. A ce que j'ai compris du probleme quand on enleve les elements dans l'ordre de notre file.

                Par exemple,

                1
                8
                1 3 20040810//notre file contient 3 20040810
                1 -1 0
                1 -1 0//plus que 1 seul 20040810
                1 3 20040920//ici elle contient 3 20040920 et 1 20040810
                1 -1 0
                1 4 20040916//ici elle contient 3 20040920 et 4 20040916
                1 -3 0
                1 -2 0//maintenant elle contient2 20040916

                 A ce que j'ai compris du code original puisque l'enoncé ne semblait pas clair du tout.

                En fait le code @mortadhasaidani1fonctionne très bien mais prends juste trop de place en memoire.

                Ce que j'ai du mal a comprendre c'est qu'on a le droit au maximum a 8000ko de memoire.

                On au maximum 300000 opérations, dans le pire des cas on stocke 300000*4 = 1 200ko de memoire.

                Normalement ca devrait largement passer.



                • Partager sur Facebook
                • Partager sur Twitter
                  27 août 2021 à 14:58:30

                  J'ai compris, j'enlevais n'importe quoi. Je dois enlever les plus anciens en premier. Je dois effectivement avoir une file par disttributeur.
                  Pour la mémoire, dans mon cas si j'ai 2 int, soit 8 bytes, ça donnerais environ 2400K, donc moins de 8000K
                  Et même si j'ai un vector de vector de array, l'information de contrôle ne devrait pas prendre tant de place que ça.
                  Supposons que c'est 32 bytes par vector et on a 20000 distributeurs. Ça donne environ 625K
                  Dans l'exemple, une vente concerne un seul item. Mais il est concevable que ce soit plus.
                  On devra peut-être piger dans les stocks de dates différentes.
                  • Partager sur Facebook
                  • Partager sur Twitter

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

                  france ioi utulisation trop important de la memoir

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