Bonjour, je suis en train de faire l'édition du concours Algoréa 2018 et je rencontre un problème avec l'exercice "Couche de peinture".
Voici le sujet du problème :
Énoncé
Un peintre est en train de repeindre la façade de votre maison. Vous l'observez effectuer des allers-retours avec son rouleau le long d'une bande horizontale.
Si l'on numérote des positions tous les centimètres le long de la bande, en commençant à 1, on peut décrire le déplacement du rouleau du peintre par une séquence de numéros de positions.
Par exemple, la séquence de positions "5 3 4 3 1 6" correspond au déplacement illustré ci-dessous. Le peintre commence à la position 5, puis va vers la position 3 sans lever son rouleau, puis repart vers la droite jusqu'à la position 4 sans lever son rouleau, puis revient à la position 3, etc. :
Écrivez un programme qui calcule et affiche le nombre maximal de couches de peinture superposées entre deux positions successives de la bande.
Dans l'exemple ci-dessus, le nombre maximal de couches est 4. Il est atteint entre les positions 3 et 4.
Entrée
La première ligne de l'entrée contient un entier nbPositions entre 2 et 20 000, le nombre de positions décrivant le parcours du rouleau de peinture.
Les nbPositions lignes suivantes contiennent chacune un entier entre 1 et 20 000. Il s'agit dess positions successives du rouleau, dans l'ordre des déplacements effectués.
Sortie
Vous devez afficher le nombre maximal de couches de peinture superposées.
Exemples
Voici un exemple d'entrée.
6
5
3
4
3
1
6
La sortie attendue est la suivante.
4
Cet exemple correspond à celui de l'énoncé.
Tests
Dans la moitié des tests, nbPositions < 100, et toutes les positions sont entre 1 et 100.
Dans l'autre moitié des tests, nbPositions < 20 000.
Limites
Limite de temps : 100 ms.
Limite de mémoire : 64000 kb.
Sur presque la moitié des tests, mon programme dépasse la limite d'exécution autorisée.
Voici mon code :
#include <iostream>
#include <utility>
using namespace std;
int main()
{
int nbPositions;
cin >> nbPositions;
int a, precedant;
int nbPassages[nbPositions] = {0};
int maxElement = 0;
for (int i = 0; i < nbPositions; i++) {
cin >> a;
if (i != 0) {
if (precedant < a) { // permet de faire des paires du plus petit au plus grand
for (int j = precedant; j < a; j++) { // passage dans chaque intervale
nbPassages[j]++;
if (nbPassages[j] > maxElement) { // stocke le nb de passages le plus grand dans maxElement
maxElement = nbPassages[j];
}
}
}
else {
for (int j = a; j < precedant; j++) { // passage dans chaque intervale
nbPassages[j]++;
if (nbPassages[j] > maxElement) { // stocke le nb de passages le plus grand dans maxElement
maxElement = nbPassages[j];
}
}
}
}
precedant = a;
}
cout << maxElement << endl;
system("PAUSE");
return 0;
}
Je me doute que la solution de mon programme est sûrement la solution naïve mais je ne vois pas comment faire...
PS : Je précise que le site du concours ne compile qu'en C++98 .
Et, dis moi, pourquoi ne créerais tu -- tout simplement -- pas un tableau qui contienne directement le nombre de couches pour chaque intervalle de 1 possible?
Il te suffirait alors, à chaque mouvement effectué par le peindre, d'augmenter le nombre de couhes présentes aux endroits sur lesquels le rouleau est passé
Je m'explique:
Mettons que tu aies vingt positions différentes, tu aurais donc un tableau de vingt entiers dont toutes les valeurs sont à 0
si le peintre passe "de la position 3 à la position 7", tu incrémente les valeurs qui se trouvent en position 3,4,5 et 6
Une fois que tous les coups de pinceaux ont été donnés, il te suffira de chercher le nombre maximal, qui coincidera avec le nombre de couches maximal
Ceci étant dit, ton code n'est pas du C++ valide, ne serait-ce que parce que tu utilise des VLA (Variable Length Arrays) qui ne sont absolument pas autorisés en C++ (ils ont été admis "quelques temps" en C, cependant, je crois que les évolutions de la norme ont également supprimé cette possibilité en C).
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Et, dis moi, pourquoi ne créerais tu -- tout simplement -- pas un tableau qui contienne directement le nombre de couches pour chaque intervalle de 1 possible?
En effet, la ce serait efficace. Mais trop simple, pas drôle !
Si j'étais l'auteur de l'énoncé, je changerais l'énoncé, je dirais que c'est entre 0.0 et 100.0 (en float), je rentrerais des nombre flottants en entrée
Et, dis moi, pourquoi ne créerais tu -- tout simplement -- pas un tableau qui contienne directement le nombre de couches pour chaque intervalle de 1 possible?
En effet, la ce serait efficace. Mais trop simple, pas drôle !
C'est un concours d'algorithmes... Le but est justement de trouver la manière la plus simple de faire quelque chose rapidement
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
J'ai trouvé amusant l'algorithme de koala01. Je l'ai d'abord codé en Python, mais le temps d'exécution est affreux. Je ne vous donnerais pas mon code. Je l'ai codé en C avec 20000 déplacements dans l'intervalle 1-20000. J'obtiens des temps de l'ordre de 50ms avec l'option -O3. Si les gens de C++ ne sont pas trop allergiques aux booléens qu'on traite comme des entiers, voici un petit truc pour ne faire qu'une boucle: J'ai les variables precedent, courant, direction, Je suppose que ça se passe d'explication. Je peux faire: direction = (precedent <= courant) * 2 - 1; for(int i=precedent; i != courant; i+=direction) tab[i]+=1;
Le Tout est souvent plus grand que la somme de ses parties.
Et, dis moi, pourquoi ne créerais tu -- tout simplement -- pas un tableau qui contienne directement le nombre de couches pour chaque intervalle de 1 possible?
Il te suffirait alors, à chaque mouvement effectué par le peindre, d'augmenter le nombre de couhes présentes aux endroits sur lesquels le rouleau est passé
C'est en fait ce que j'ai essayé de faire avec la sous boucle de mon programme (le tableau qui continent chaque couche est nbPassages que j'incrémente de 1 pour chaque nombre de l'intervalle).
PierrotLeFou a écrit:
J'ai les variables precedent, courant, direction, Je suppose que ça se passe d'explication. Je peux faire: direction = (precedent <= courant) * 2 - 1; for(int i=precedent; i != courant; i+=direction) tab[i]+=1;
Je n'ai pas compris cette partie pourrais-tu réexpliquer stp.
J'ai modifié un peu mon code (surtout pour qu'il devienne un peu plus clair) mais rien de significatif pour que le pourcentage de réussite bouge (toujours 55%) :
#include <iostream>
#include <utility>
using namespace std;
const int TAILLE_MAX = 20000;
int nbPassages[TAILLE_MAX] = {0};
int main()
{
int nbPositions;
cin >> nbPositions;
int a, precedant;
int maxElement = 0;
for (int i = 0; i < nbPositions; i++) {
cin >> a;
if (i != 0) {
for (int j = min(precedant, a); j < max(precedant, a); j++) { // passage dans chaque intervalle du plus petit au plus grand nombre
nbPassages[j]++;
}
}
precedant = a;
}
for (int i = 0; i < nbPositions; i++) {
if (nbPassages[i] > maxElement) {
maxElement = nbPassages[i];
}
}
cout << maxElement << endl;
system("PAUSE");
return 0;
}
Je ne sais pas vraiment comment résoudre ce problème...
Tu fais une boucle de min(precedent, a) jusqu'à max(precedent, a) De cette façon, ta boucle est toujours en direction du plus petit jusqu'au plus grand. Moi, je parcours la boucle du precedent jusqu'au courant (que tu appelles a). Je peux donc parcourir en ordre croissant ou décroissant. Il n'y a pas forcément d'avantage majeur dans la façon dont je le fais. Dans ton cas, la limite supérieure doit être évaluée à chaque tour de boucle. Par contre, tu augmentes ton indice de 1, ce qui est légèrement plus rapide que d'augmenter (ou diminuer) de la valeur direction comme je l'ai fait. Ton code C++ devrait être maintenant aussi rapide que mon code C. En plus, je générais les déplacements de façon aléatoire, alors que le tien le saisit de l'input standard.
Le Tout est souvent plus grand que la somme de ses parties.
Tu fais une boucle de min(precedent, a) jusqu'à max(precedent, a) De cette façon, ta boucle est toujours en direction du plus petit jusqu'au plus grand. Moi, je parcours la boucle du precedent jusqu'au courant (que tu appelles a). Je peux donc parcourir en ordre croissant ou décroissant. Il n'y a pas forcément d'avantage majeur dans la façon dont je le fais. Dans ton cas, la limite supérieure doit être évaluée à chaque tour de boucle. Par contre, tu augmentes ton indice de 1, ce qui est légèrement plus rapide que d'augmenter (ou diminuer) de la valeur direction comme je l'ai fait. Ton code C++ devrait être maintenant aussi rapide que mon code C. En plus, je générais les déplacements de façon aléatoire, alors que le tien le saisit de l'input standard.
Ha ok maintenant j'ai compris merci pour cette explication.
Personne n'aurait une piste à donner pour ce problème car je suis un peu bloqué ?
Mon code n'a toujours pas avancé depuis mon dernier message...
ttSi ça n'est pas un sacrilège que de poster du code C non inddenté dans une catégorie sur C++, voici ce que j'ai fait: - #include <stdio.h> #include <stdlib.h> #include <time.h> int main(){ int tab[20000]; clock_t t0=clock(); srand(time(NULL)); for(int i=0;i<20000; i++) tab[i]=0; int p=0; for(int i=0; i<20000;i++){ int c=rand()%20000; int d=(p<=c)*2-1; for(int j=p; j!=c; j+=d) tab[j]+=1; p=c; } int m=0; for(int i=0; i<20000; i++) if(m<tab[i]) m=tab[i]; printf("%d\n",m); printf("temps: %d\n",clock()-t0); return(0); }
Le Tout est souvent plus grand que la somme de ses parties.
J'essaie de juste comprendre comment vous tester le temps et la mémoire utilisée par l'algo?
pour le temps j'ai essayer le code suivant, est ce que je suis dans le bon ou à côté de la plaque ? :
#include <iostream>
#include <utility>
#include <chrono>
int main()
{
int nbPositions;
std::cout << "Entrez nombre passage : ";
std::cin >> nbPositions;
int a, precedant;
std::chrono::high_resolution_clock::time_point ta;
int nbPassages[nbPositions] = {0};
int maxElement = 0;
for (int i = 0; i < nbPositions; i++) {
std::cout << "entrez a : "; std::cin >> a;
ta= std::chrono::high_resolution_clock::now();
if (i != 0) {
if (precedant < a) { // permet de faire des paires du plus petit au plus grand
for (int j = precedant; j < a; j++) { // passage dans chaque intervale
nbPassages[j]++;
if (nbPassages[j] > maxElement) { // stocke le nb de passages le plus grand dans maxElement
maxElement = nbPassages[j];
}
}
}
else {
for (int j = a; j < precedant; j++) { // passage dans chaque intervale
nbPassages[j]++;
if (nbPassages[j] > maxElement) { // stocke le nb de passages le plus grand dans maxElement
maxElement = nbPassages[j];
}
}
}
}
precedant = a;
}
std::cout << maxElement << std::endl;
std::chrono::high_resolution_clock::time_point tb= std::chrono::high_resolution_clock::now();
unsigned int time= std::chrono::duration_cast<std::chrono::microseconds>(tb - ta).count();
std::cout << time << " microseconds!" << std::endl;
system("PAUSE");
return 0;
}
Pour accélérer, je te propose de compter que dans un sens, par exemple les descendant et de multiplier par deux.
Je m'explique si tu fermes la première borne avec la dernière tu as forcement un nombre pair de couches.
Il faudra juste faire un ajustement entre ces deux bornes (première et dernière).
Un schémas :
- Edité par rouloude il y a environ 19 heures
Excellente idée merci beaucoup rouloude. J'aurais tout de même une question, comment savoir si il faut ajouter 1 au dernier intervalle ou premier ?
Je ne sais pas du tout comment le mettre en place, j'ai tout de même fait un petit programme qui ne passe que 15 % des tests mais qui ne change rien par rapport aux limites de temps d'exécution :
#include <iostream>
#include <utility>
using namespace std;
const int TAILLE_MAX = 20000;
int nbPassages[TAILLE_MAX] = {0};
int main()
{
int nbPositions;
cin >> nbPositions;
int a, precedant;
int maxElement = 0;
for (int i = 0; i < nbPositions; i++) {
cin >> a;
if (i != 0 && precedant > a) {
for (int j = a; j < precedant; j++) { // passage dans chaque intervale de a à precedant
nbPassages[j]++;
}
}
precedant = a;
}
for (int i = 0; i < nbPositions; i++) {
if (nbPassages[i] > maxElement) {
maxElement = nbPassages[i];
}
}
cout << maxElement * 2 << endl;
//system("PAUSE");
return 0;
}
Il me semble pourtant que je limite le nombre de passages dans la boucle ce qui devrait faire baisser le temps d'exécution...
Ce qui coûte cher, c'est de parcourir les intervalles. S'il y avait un truc pour compter les intervalles emboîtés seulement, ce serait sans doute plus rapide. Sauf qu'on pourrait avoir plus d'une série d'intervalles emboîtés. Ou des intervalles qui se chevauchent. Comment compter tout ça?
Le Tout est souvent plus grand que la somme de ses parties.
#include <vector>
#include <iostream>
#include <limits>
#include <algorithm>
#include <random>
static constexpr size_t rangeCount{30}; // should be 20 000 for the site
size_t askPasses(){
while(true){
std::cout<<"combien de positions voulez vous?";
std::string temp;
std::getline(std::cin, temp);
size_t idx{0};
auto result = std::stoul(temp, &idx);
if(!temp.empty() && idx ==temp.size())
return result;
std::cerr<<"veuillez introduire un nombre d'positions valides\n";
std::cin.clear();
std::cin.ignore( std::numeric_limits<std::streamsize>::max(), '\n' );
}
}
/* define randomly next end interval */
size_t randomizeRange(){
static std::random_device rd;
static std::mt19937 gen{rd()};
static std::uniform_int_distribution<size_t> distrib(1, rangeCount);
return distrib(gen);
}
void countPasses(std::vector<size_t> & ranges, size_t start, size_t end){
auto min = std::min(start, end);
auto max = std::max(start, end);
for(auto i = min; i<max; i++){
ranges[i]++;
}
}
void printPasses(std::vector<size_t> const & ranges){
for(size_t i = 0; i<ranges.size(); ++i)
std::cout<<"intervalle "<<i<<" : "<< ranges[i] <<" passes\n";
}
void printMaxPasses(std::vector<size_t> const & ranges){
auto max = std::max_element(ranges.begin(), ranges.end());
std::cout<<" max passes :"<<*max<<" at position "<<std::distance(ranges.begin(), max)<<"\n";
}
void printMinPasses(std::vector<size_t> const & ranges){
auto min = std::min_element(ranges.begin(), ranges.end());
std::cout<<" max passes :"<<*min<<" at position "<<std::distance(ranges.begin(), min)<<"\n";
}
int main(){
std::vector<size_t> ranges;
ranges.resize(rangeCount, 0);
size_t max =askPasses();
size_t start{0};
for(size_t i = 0; i< max; ++i){
size_t end = randomizeRange();
countPasses(ranges, start, end);
start = end;
}
printPasses(ranges);
printMaxPasses(ranges);
printMinPasses(ranges);
}
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Je verrais dans un premier temps un tableau d'intervalles, genre tab[20000][2] Et je le trierais comment? D'abord par la borne inférieure, mais ensuite ... ? Il faudrait voir le coût du tri. Mais on ne ferait à mon avis qu'un seul passage ensuite.
Le Tout est souvent plus grand que la somme de ses parties.
Bon j'arrive doucement, attendez moi lol je suis vais commencer bloc de quatre maintenant.
c'est un super entrainement quand même je trouve, si antoine était pas venu poser une question je connaissait même pas ce site. surtout que ça oblige à écrire et pas de debbug intégré.
Car il compile et il s'exécute parfaitement sur mon PC, sous Gcc 10.0.2 (cependant, il devrait compiler avec tout compilateur "récent", dans le cas présent, qui supporte la norme C++11)
Il ne donne aucun résultat?
Car je croyais avoir été clair dans le seul commentaire que j'ai écrit: j'utilise ici une fonction de génération aléatoire de la position suivante dans la liste, et donc, sur le fait qu'il faudra prévoir une autre fonction pour la récupération des positions en fonction de la manière dont elles sont transmises par le site
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Une petite correction de la fonction main (qui prend désormais directement les introductions à partir de l'entrée standard) et une adaptation de la fonction printMaxPasses pour que l'affichage corresponde au format attendu...
void printMaxPasses(std::vector<size_t> const & ranges){
auto max = std::max_element(ranges.begin(), ranges.end());
std::cout<<*max<<"\n";
}
int main(){
std::vector<size_t> ranges;
ranges.resize(rangeCount, 0);
size_t max ;
std::cin>>max;
size_t start{0};
std::cin>>start;
for(size_t i = 1; i< max; ++i){
size_t end;
std::cin>> end;
countPasses(ranges, start, end);
start = end;
}
printMaxPasses(ranges);
}
Cela devrait désormais aller bien mieux, non?
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
× 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.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
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.
for ( size_t nbMembre : membreForum ) { std::cout << "Bonjour ! \n"; }
for ( size_t nbMembre : membreForum ) { std::cout << "Bonjour ! \n"; }
for ( size_t nbMembre : membreForum ) { std::cout << "Bonjour ! \n"; }
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.
for ( size_t nbMembre : membreForum ) { std::cout << "Bonjour ! \n"; }