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 :
le numéro du distributeur sur lequel porte l'opération ;
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) ;
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.
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.
Le Tout est souvent plus grand que la somme de ses parties.
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 ) . Ton code ne respecte pas cette contrainte, c'est pourquoi j'utilise std::string au lieu de int.
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; }
Le Tout est souvent plus grand que la somme de ses parties.
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.
@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.
Le Tout est souvent plus grand que la somme de ses parties.
@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.
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.
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é.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
En recherche d'emploi.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.