dite j'ai une question a propos de 42 000 000 ( j'ai passer les 100%) MAIS un truc m'intrigue : la première fois je fais 94% ( test 16 délais dépasser) je re essaie avec le même code, bam 100% ; Tant mieux mais j'ai pas saisit pourquoi; Est ce que leur machine peut avoir ramer ? lol
D'accord, oui ca diminue, mais je suis visiblement fatigué car j'avais déjà mal lu l'énoncer, je ferais ça demain;
Edit: j'ai commencer un peu ce matin avant de partir( pas bcp le temps le matin) normalement ce soir ca devrait être bon j'ai presque terminer parcour numero 2; J'espere; Je vous tiens au courant tout à l'heure;
" EDIT : je remet le code sans "numberBis" qui servait à rien; "
Me re voila, j'était occuper quand j'avais le temps d'essayer couche de peinture, celui la il est du genre corsé lol; Jusque la rien ne fonctionnais, mais, j'ai enfin réussi à écrire un code qui trouve au moins les bonne réponse, mais très loin de valider les tests;
maintenant je vais chercher à l'améliorer, je doit changer de méthode pour le entrée car à partir du 12 jusque 20 j'ai accès mémoire invalide, même si je laisse que les entrées de mon code j'ai un vector avec sans doute + que 20 000 entrée; d'ailleurs numberBis devais résoudre ça mais c'était pas le cas;
voila mon code à 20% , j'ai vraiment essayer de faire différemment, mais je suis pas sur la bonne route je pense, mais j'ai d'autre idées encore :
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
int entryNumber = 0;
std::cin >> entryNumber;
std::vector <int> number ;
int nb = 0;
int previous = 0;
for (int i=0; i<entryNumber; ++i)
{
number.push_back(0);
std::cin >> number[i];
nb = number[i];
if(i>0)
{ previous=number[i-1];
if ( previous>nb && previous != nb+1 )
{
--i; --entryNumber; number.pop_back(); while(previous!=nb) { --previous;++i;++entryNumber; number.push_back(previous); }
}
if (previous<nb && previous != nb-1)
{
--i; --entryNumber; number.pop_back(); while(previous!=nb) { ++previous;++i;++entryNumber; number.push_back(previous); }
}
}// if i>0
}//for
// ici numberBis == 5,4,3,4,3,2,1,2,3,4,5,6
// - - - - - -
size_t numberSize = number.size();
std::vector<int> blockOfTwo;
std::vector<int>::iterator start = number.begin();
std::vector<int>::iterator ends = number.begin()+2;
std::vector<int>::iterator endsBis = number.begin()+1; // rajout de derniere minute pour if ( (*start)!= (*endsBis) || (*blockOfTwo.begin())!= (*twoEndBis))
std::vector<int>::iterator twoBegin = number.begin();
std::vector<int>::iterator twoEnd = number.begin()+2;
blockOfTwo .insert(blockOfTwo.begin(), twoBegin, twoEnd); //premier bloc de 2
int total = 0;
int counter = 0;
std::vector<int>::iterator twoEndBis = blockOfTwo.begin()+1; // rajoutBis de derniere minute pour if ( (*start)!= (*endsBis) || (*blockOfTwo.begin())!= (*twoEndBis))
for (size_t i=0; i<numberSize-1; ++i)
{
for (size_t j=0; j<numberSize-1; ++j)
{
if ( (*start)!= (*endsBis) || (*blockOfTwo.begin())!= (*twoEndBis))
{
if (std::equal(start, ends, twoBegin) ) { ++start; ++ends; ++counter; }
if (std::equal(start, ends, blockOfTwo.rbegin()) ) { ++start; ++ends; ++counter; }
else { ++start; ++ends; }
}//if
}//for
if (counter > total) { total = counter; }
start = number.begin(); //remise à 0
ends = number.begin()+2;
counter = 0;
blockOfTwo.clear();
++twoBegin; //bloc de 2 suivant
++twoEnd;
blockOfTwo.insert(blockOfTwo.begin(), twoBegin, twoEnd);
}
std::cout << total;
return 0;
}
voila j'ai réussi ,,, à gagner 10% sur les 20% que j'avais déjà lol; J'ai écrit un code différent que le précédent, je passe 30% des tests, à partir du test 7 j'ai les mauvaise réponse ( "48" au lieu de "50" ); c'est pas grave j'ai pas encore beaucoup travailler ce code ( a partir du 12 je dépasse la limite de temps ), ça je chercherais quand j'aurais déjà les bonne réponse à tout les autres test; En attendant je poste quand même mon code, comme j'arrête pour aujourd'hui;
petite question ,dans les conditions de mon code j'ai " c1 && c2 && c3 && c4 " comment doit-je mettre les parenthèse ? " (c1 && c2) && c3 && c4 " ou "( ( c1 && c2) && c3) && c4 " ?
30%
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
int entryNumber = 0;
std::cin >> entryNumber;
std::vector <int> number ;
for (int i=0; i<entryNumber; ++i)
{
number.push_back(0);
std::cin >> number[i];
}
std::vector<int>::iterator in = number.begin();
std::vector<int>::iterator out = number.begin()+1;
std::vector<int>::iterator first = number.begin();
std::vector<int>::iterator last = number.begin()+1;
int coatCounter = 0;
int coatCounterMax = 0;
for (int i=0; i<entryNumber/2; ++i)
{
coatCounter = 0; //std::cout<< *first << "," << *last << std::endl;
for (int j=0; j<entryNumber-1; ++j)
{
if ( (*first) != (*last) && (*first) <= (*in) && (*first) >= (*out) && (*last) <= (*in) && (*last) >= (*out) )
{
++coatCounter;
}
else if ( (*first) != (*last) && (*first) >= (*in) && (*first) <= (*out) && (*last) >= (*in) && (*last) <= (*out) )
{
++coatCounter;
}
++in; ++out;
}
in = number.begin();
out = number.begin()+1;
first += 2;
last += 2;
if ( coatCounter > coatCounterMax) {coatCounterMax = coatCounter;}
}
std::cout << coatCounterMax << std::endl ;
return 0;
}
tu n'est en fait absolument pas obligé de mettre de parenthèses dans ce cas là, car l'opérateur && est un opérateur "optimisé":
C'est à dire que la première condition va être évaluée... en premier, et que les conditions suivantes ne seront évaluées que... si le résultat a "encore une chance" de changer en fonction de l'entrée à tester.
Or, la table de vérité de l'opérateur && ressemble à ceci:
A | B | A && B
-----+-----+--------
faux |faux | faux
faux |vrai | faux
vrai |faux | faux
vrai |vrai | vrai
Comme tu peux le constater, sur les quatre combinaisons possibles, il n'y en a qu'une seule qui fournit un résultat différent (c'est quand les deux entrées sont vraies que la sortie est vraie). C'est ce que l'on appelle "l'état unique" de cet opérateur
Si tu veux tester A && B && C && D, B ne sera testé que si A est vrai, car, autrement, le résultat sera d'office faux. De même, C ne sera testé que (si A est déjà vrai et) si B est vrai, pour la même raison. Enfin, D ne sera testé que (si A et B sont déjà vrais et) si C est vrai... Mais bon, tu auras compris le principe, n'est-ce pas ?
Il en va de même avec l'opérateur ||, qui est un OU optimisé, et dont la table de vérité ressemble à
A | B | A || B
-----+-----+--------
faux |faux | faux
faux |vrai | vrai
vrai |faux | vrai
vrai |vrai | vrai
Comme tu peux le constater l'état unique est sur le faux.
La différence d'avec l'opérateur && est que, si tu as une condition A || B || C || D, B ne sera évalué que si A est déjà faux à la base et ainsi de suite, autrement, le fait de tester B (et les suivants) ne changera de toutes manières plus rien au résultat.
C'est d'ailleurs grâce au fait que ces deux opérateurs sont optimisés que l'on pourrait parfaitement écrire un code proche de
void foo(MaClasse * obj){
if(obj && obj->isAlive()){ /* sous etendu :
* if(obj!=nullptr &&
* obj->isAlive())
*/
/* ce qu'il faut faire */
}
}
sans risquer de "tout faire péter" suite au déréférencement d'une adresse invalide
Enfin, il faut savoir que, tout comme il existe des règles de priorités entre le +(addition) et le * (multiplication), il existe des règles de priorités entre || et &&, avec la priorité donnée à l'opérateur &&.
Si donc, tu devais avoir une condition "biscornue" du genre de A || B && C || D, elle serait d'office évaluée comme si tu avais placé les parenthèses sous la forme de A || (B && C) || D.
Au final, nous pourrions donc dire que les parenthèses ne sont "jamais" indispensables, pour autant que tu tiennes correctement compte de la priorité des opérateurs.
Par contre, dés le moment où tu te mets à mélanger les opérateur || avec les opérateurs &&, les parenthèses deviennent très rapidement utiles, que ce soit pour expliciter le fait que les priorités sont respectées ou, justement, pour modifier l'ordre des priorités et t'assurer que les différentes conditions soient testées "dans l'ordre dont tu as besoin"
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
Bon, une autre solution pour accélérer la boucle principale : pour éviter de faire des grandes boucles pour incrémenter le tableau de compteur de couche, pour toute distance de parcours du pinceau supérieur à la moitié de la distance maximum, compter avec un compteur de couche complète à part, et dans ce cas décrémenter les cases du tableau de compteur où le pinceau n'est pas passé !
Exemple sur une distance maxi de 20000 et un parcours de 1 à 20000 on incrémente une seule variable. et sur un parcours de 2 à 20000 on incrémente la dite variable et décrément seulement la case du tableau correspondant à l’intervalle 1.
je viens d'atteindre 60% je pense avoir trouver le bon filon, bon la j'ai encore des bugs car je fusionne plusieurs de mes essais, et en vrai je m'attendais pas à ce que ça marche, du coup demain je referait ça correctement car il est l'heure pour moi d'allez devant la télé;
Oui , en fait ca s'explique par le fait que en dernière minute avant d'arrêter pour aujourd'hui j'ai modif une double boucle imbriquées en simple boucle sans tout remettre correctement. j'etait trop fatiguer apparement. Demain ( tantôt) je réécrit ce code correctement =)
bon j'ai pas encore les 100% mais ça prend forme, je doit encore améliorer mon code, maintenant j'atteint les 70%, mais il y as du bon, je ne dépasse plus les 100ms, jusque que j'ai quelque mauvaise réponse (7, 8, 12, 13, 14, 15) le reste est ok, je vais résoudre ça j'espère très bientôt; en attendant voici mon code actuel ( non terminé )
EDIT : j'ai réussi à sortir les entrée du test 7 ( pour débug mon code ) les voici :
Sortir les entrées ca as été facile comme mon programme affichait 69 au lieu de 50, j'ai mit un condition "if (layerCounter==69). { boucle for qui imprime les entrées}"
Sinon pour l'algo, ce que j'al fait c'est si :
pour " 5,3,4,3,1,,6 ": mes intervalles sont [5,3] [3,4] [4,3] [3,1] [1,6]
si 4 est > que 3 && 4 <= que 5 alors on est repassé au même endroit; je sauvegarde 3,4;
si 3 < que 4 && 3 >= 3 on est repassé au même endroit on sauvegarde 4,3
si 1 < que 3 && 1 < 4 && 3 !> 3 aucune condition vérifiée on est pas repassé, on garde 4,3
si 6 > que 4 && 6 > 3 && 1 < 3 alors on repasse au même endroit ce qui donne 4
voila l'idée ;
depuis j'ai modifier la manière dont mon programme enregistre les entrées, si par exemple les entrées sont 6,5,4,3,2,1; ma structure contiendra que "[6,1]" par exemple ou pour 5,3,4,3,1,6 j'ai [5,3] [3,4] [4,1] [1,6]
ce qui ne chang pas les mauvaises réponses de mon code mais ça réduit déjà le nombre d'intervalle.
le problème qu'il me reste à résoudre a ce stade dans ce code c'est pour l'instant si on a par exemple 50 passage sur 5,4 et 30 sur 8,9 la reponse sera 80 au lieu de 50;
le problème qu'il me reste à résoudre a ce stade dans ce code c'est pour l'instant si on a par exemple 50 passage sur 5,4 et 30 sur 8,9 la reponse sera 80 au lieu de 50;
C'est à se demander ce que l'on t'as appris depuis que tu es ici...
Les quatre grandes étapes de l'écriture d'un code sont
écrire du code lisible, car, si le code n'est pas lisible, la suite sera pour ainsi dire impossible
écrire un code correct, car si le code n'est déjà pas correct, il y a peu de chances que la suite ne fonctionne
d'écrire un code qui fait ce que l'on attend de lui, car si ce point n'est pas respecter lorsque l'on passe à la suite, tout ce que l'on aura, c'est un code qui nous envoie rapidement dans le mur, et ce n'est pas ce qu'il y a de plus utile
d'avoir un code rapide: une fois qu'il est lisible et correct, une fois que les résultats obtenus correspondent à ceux que l'on attendait, et seulement à ce moment là, il devient possible d'essayer de faire en sorte que le code soit rapide.
Et ces étapes doivent être effectuées dans cet ordre bien particulier, à l'exception de tout autre
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
Parce ce que ce que tu me dit c'est déjà fait, mais à part les 55% comme vous ça marche pas mieux du coup j'essaie autre choses mais c'est pas si facile; l'autre code ce sont des expérimentations j'ai pas encore pris le temps de le rendre plus lisible;
voila mon code qui donne les bonne réponse mais qui est trop lent :
#include <iostream>
#include <algorithm>
#include <vector>
struct layer {int first, ends;};
int main()
{
int entryNumber = 0;
std::cin >> entryNumber;
std::vector<int> allLayer (entryNumber, 0);
layer number [entryNumber-1];
for (int i=0; i<entryNumber-1; ++i)
{
if (i==0)
{
std::cin >> number[i].first; // Première && deuième entrée
std::cin >> number[i].ends;
}
if (i>0) // A partir de la troisième entrée
{
number[i].first = number[i-1].ends;
std::cin >> number[i].ends;
// si first < ends on va de G à D si first < ends on va toujours de G à D
if ( number[i-1].first < number[i-1].ends && number[i].first < number[i].ends )// de gauche à droite
{
number[i-1].ends = number[i].ends; --i; --entryNumber;
}
else if ( number[i-1].first > number[i-1].ends && number[i].first > number[i].ends )// de droite à gauche
{
number[i-1].ends = number[i].ends; --i; --entryNumber;
}
}
}//for
for( int i=0; i<entryNumber-1; ++i)
{
if ( number[i].first > number[i].ends )
{
while (number[i].first != number[i].ends-1) { ++allLayer[ number[i].first -1]; --number[i].first; }
}
else if ( number[i].first < number[i].ends )
{
while (number[i].first != number[i].ends+1) { ++allLayer[ number[i].first -1]; ++number[i].first; }
}
}
std::greater<int> fonctor;
std::sort(allLayer.begin(),allLayer.end(), fonctor);
std::cout << allLayer[0];
return 0;
}
Déjà, vire ton premier test (lignes 16 à 20) de ta boucle et adapte ta boucle en conséquence, car, c'est un test qui ne sert au final à rien, vu qu'il va à peu près tout le temps donner le même résultat : faux, tout en t'obligeant à faire le test suivant qui, lui, donnera presque toujours le même résultat: vrai; le tout rendant ton code inutilement complexe (tant à l'exécution, bien que l'on puisse espérer que le compilateur fera des optimisations, mais surtout à la lecture )
De plus, tes else if (lignes 32 et 47) ne sont pas correctement indentés, car il correspondent respectivement à la partie else du test qui se trouvent aux lignes 27 et 42 (en confrontation directe avec la première étape à respecter :D)
Ensuite, vire moi cet affreux VLA de la ligne 13 : ce genre de pratique n'a jamais été accepté en C++, et, si elle a bel et bien été acceptée en C pendant deux ou trois ans, ils ont très rapidement fait machine arrière
Enfin, si c'est pour faire deux boucles dans ta fonction, peut-être devrais tu envisager de respecter le SRP et de créer une fonction qui s'occupe de la première boucle (la saisie des couches) et une autre qui s'occupe de la deuxième boucle (le comptage des boucles).
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 corriger cela, j'ai un doute pour l'indentation si c'est mieux, pour le reste il n'y a plus de VLA, j'ai plutôt créé un tableau d'intervalle, j'ai créé les fonctions pour les boucles et ajouté des retours à la lignes dans conditions quand il y à "&&" et dans certains blocs; J'ai gardé "struct" car pour une autre version de mon code ca me sera utile pour tentez une autre approche sans incrémenter de tableau( pas sur que ca va marcher); n'hésitez pas à me corriger de nouveau si besoin ! ;
#include <iostream>
#include <algorithm>
#include <vector>
struct layer {int first, ends;};
void entry (std::vector<layer> &number, int &entryNumber)
{
std::cin>> number[0].first;
std::cin>> number[0].ends;
for (int i=1; i<entryNumber-1; ++i)
{
number[i].first = number[i-1].ends;
std::cin >> number[i].ends;
if ( number[i-1].first < number[i-1].ends &&
number[i].first < number[i].ends ) // de gauche à droite
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number.pop_back();
}
else if ( number[i-1].first > number[i-1].ends &&
number[i].first > number[i].ends ) // de droite à gauche
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number.pop_back();
}
}
}
void layerCounter(std::vector<layer> &number, std::vector<int> &allLayer, int &entryNumber)
{
for ( int i=0; i<entryNumber-1; ++i)
{
if ( number[i].first > number[i].ends )
{
while (number[i].first != number[i].ends-1)
{
++allLayer[ number[i].first -1];
--number[i].first;
}
}
else if ( number[i].first < number[i].ends )
{
while (number[i].first != number[i].ends+1)
{
++allLayer[ number[i].first -1];
++number[i].first;
}
}
}
}
int main()
{
int entryNumber = 0;
std::cin >> entryNumber;
std::vector<int> allLayer (entryNumber, 0);
std::vector<layer> number (entryNumber-1, layer());
entry(number, entryNumber);
layerCounter(number, allLayer, entryNumber);
std::cout << *std::max_element(allLayer.begin(), allLayer.end() );
return 0;
}
j'ai enfin réussi à écrire un code qui n'incrémente pas de tableau et qui trouve quand même les bonnes réponse, mais qui dépasse quand même le temps imparti à partir du test 12; Bien sur j'ai fait plus d'un essais en allégeant mon code du "length" et du stable sort, mais j'ai pas eu de grand changement; j'ai trier les intervalles du plus petit au plus grand en utilisant "stable_sort" creer une surcharge de ma fonction "compareAndLayerCounter" affin de réduire les passages dans la boucle en espérant que les plus petits intervalles les plus superposées serais dans le début, mais ce n'est pas le cas sauf pour le test 17 et 20 ( 65% en bidouillant la boucle principale de "compareAndLayerCounter" ) enfin tout ça ce sont des essais pour tentez de passer tout les benchmark; Dans la boucle principale de "compareAndLayerCounter" je peux passer max 500 fois sans dépasser le temps imparti, mais ce n'est pas suffisant ;
je vais poster 3 version de mon code, la version originale, la version allégée, et la version "bidouillage";
Pour la version original, est ce que c'est la bonne manière d'écrire en respectant l'indentation, SRP, et convention? ( en sachant que j'ai ecrit le code pour algoréa)
code original : (55%)
#include <iostream>
#include <algorithm>
#include <vector>
class Layer
{ /* class qui lit les entrées && calcul "length" && réduit les entrées du genre "5,4,3,2 en 5,2" */
public :
void inputEntry (std::vector<Layer> &number, int &entryNumber)
{
std::cin >> number[0].first; // Première && deuxième entrée
std::cin >> number[0].ends;
// Calcul de la longueur de l'interval pour les trier par la suite
if ( number[0].first>number[0].ends )
{
number[0].length = number[0].first -number[0].ends;
}
else
{
number[0].length = number[0].ends -number[0].first;
}
for (int i=1; i<entryNumber-1; ++i)
{ // A partir de la troisième entrée
number[i].first = number[i-1].ends;
std::cin >> number[i].ends;
if ( number[i].first>number[i].ends )
{
number[i].length = number[i].first -number[i].ends;
}
else
{
number[i].length = number[i].ends -number[i].first;
}
// si first < ends on va de G à D si first < ends on va toujours de G à D
if ( number[i-1].first < number[i-1].ends && number[i].first < number[i].ends )// de gauche à droite
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number[i].length = number[i].ends -number[i].first;
number.pop_back();
}
else if ( number[i-1].first > number[i-1].ends && number[i].first > number[i].ends )// de droite à gauche
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number[i].length = number[i].first -number[i].ends;
number.pop_back();
}
}//for
}
int getFirst (std::vector<Layer> &number, int i)
{
return number[i].first;
}
int getEnds (std::vector<Layer> &number, int i)
{
return number[i].ends;
}
int getLength ()
{
return length;
}
private :
int first;
int ends;
int length;
};
class Counter /* class qui compte les superposition de couche de peinture */
{
public :
int compareAndLayerCounter (Layer &layers, std::vector<Layer> &number, int &entryNumber)
{
int counter = 0;
int maxCounter = 0;
if ( number.size() == 1)
{
maxCounter = 1;
}
else
{
for ( int i=0; i<entryNumber-1; ++i)
{
if (layers.getFirst(number, i) != layers.getEnds(number, i)) // Si pas 1,1 par exemple
{
counter = 0;
for (int j=0; j<entryNumber-1; ++j)
{
if ( (layers.getFirst(number, i) >= layers.getFirst(number, j) && layers.getEnds(number, i) <= layers.getEnds(number, j) && layers.getFirst(number, i) <= layers.getEnds(number, j) ) // 25,24 comparer avec 20,30 par exemple
||
(layers.getFirst(number, i) >= layers.getEnds(number, j) && layers.getEnds(number, i) <= layers.getFirst(number, j) && layers.getFirst(number, i) <= layers.getFirst(number, j)) ) // 25,24 comparer avec 30,20 par exemple
{
++counter;
}
}//for j
if ( counter > maxCounter )
{
maxCounter = counter;
}
}//if
}//for i
}//else
return maxCounter;
}
};
bool compareLength (Layer one, Layer two) /* Fonction qui compare les longueurs d'intervalles de la plus petite à la plus grande */
{
return one.getLength() < two.getLength();
}
int main()
{
int entryNumber = 0;
Layer layers;
Counter counters;
std::cin >> entryNumber;
std::vector<Layer> number (entryNumber-1, Layer() );
layers.inputEntry(number, entryNumber); // lecture des entrées
std::stable_sort(number.begin(), number.begin()+entryNumber-1, compareLength); // tri du plus petit interval au plus grand
std::cout << counters.compareAndLayerCounter(layers, number, entryNumber); // compter && afficher le maximum de couche de peinture superposée au même endroit
return 0;
}
code allégé : (55%)
#include <iostream>
#include <algorithm>
#include <vector>
class Layer
{ /* class qui lit les entrées && réduit les entrées du genre "5,4,3,2 en 5,2" */
public :
void inputEntry (std::vector<Layer> &number, int &entryNumber)
{
std::cin >> number[0].first; // Première && deuxième entrée
std::cin >> number[0].ends;
for (int i=1; i<entryNumber-1; ++i)
{ // A partir de la troisième entrée
number[i].first = number[i-1].ends;
std::cin >> number[i].ends;
// si first < ends on va de G à D si first < ends on va toujours de G à D
if ( number[i-1].first < number[i-1].ends && number[i].first < number[i].ends )// de gauche à droite
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number.pop_back();
}
else if ( number[i-1].first > number[i-1].ends && number[i].first > number[i].ends )// de droite à gauche
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number.pop_back();
}
}//for
}
int getFirst (std::vector<Layer> &number, int i)
{
return number[i].first;
}
int getEnds (std::vector<Layer> &number, int i)
{
return number[i].ends;
}
private :
int first;
int ends;
};
class Counter /* class qui compte les superposition de couche de peinture */
{
public :
int compareAndLayerCounter (Layer &layers, std::vector<Layer> &number, int &entryNumber)
{
int counter = 0;
int maxCounter = 0;
if ( number.size() == 1)
{
maxCounter = 1;
}
else
{
for ( int i=0; i<entryNumber-1; ++i)
{
if (layers.getFirst(number, i) != layers.getEnds(number, i)) // Si pas 1,1 par exemple
{
counter = 0;
for (int j=0; j<entryNumber-1; ++j)
{
if ( (layers.getFirst(number, i) >= layers.getFirst(number, j) && layers.getEnds(number, i) <= layers.getEnds(number, j) && layers.getFirst(number, i) <= layers.getEnds(number, j) ) // 25,24 comparer avec 20,30 par exemple
||
(layers.getFirst(number, i) >= layers.getEnds(number, j) && layers.getEnds(number, i) <= layers.getFirst(number, j) && layers.getFirst(number, i) <= layers.getFirst(number, j)) ) // 25,24 comparer avec 30,20 par exemple
{
++counter;
}
}//for j
if ( counter > maxCounter )
{
maxCounter = counter;
}
}//if
}//for i
}//else
return maxCounter;
}
};
int main()
{
int entryNumber = 0;
Layer layers;
Counter counters;
std::cin >> entryNumber;
std::vector<Layer> number (entryNumber-1, Layer() );
layers.inputEntry(number, entryNumber); // lecture des entrées
std::cout << counters.compareAndLayerCounter(layers, number, entryNumber); // compter && afficher le maximum de couche de peinture superposée au même endroit
return 0;
}
code bidouillage : (65%) ( sert a rien sinon)
#include <iostream>
#include <algorithm>
#include <vector>
class Layer
{ /* class qui lit les entrées && calcul "length" && réduit les entrées du genre "5,4,3,2 en 5,2" */
public :
void inputEntry (std::vector<Layer> &number, int &entryNumber)
{
std::cin >> number[0].first; // Première && deuxième entrée
std::cin >> number[0].ends;
// Calcul de la longueur de l'interval pour les trier par la suite
if ( number[0].first>number[0].ends )
{
number[0].length = number[0].first -number[0].ends;
}
else
{
number[0].length = number[0].ends -number[0].first;
}
for (int i=1; i<entryNumber-1; ++i)
{ // A partir de la troisième entrée
number[i].first = number[i-1].ends;
std::cin >> number[i].ends;
if ( number[i].first>number[i].ends )
{
number[i].length = number[i].first -number[i].ends;
}
else
{
number[i].length = number[i].ends -number[i].first;
}
// si first < ends on va de G à D si first < ends on va toujours de G à D
if ( number[i-1].first < number[i-1].ends && number[i].first < number[i].ends )// de gauche à droite
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number[i].length = number[i].ends -number[i].first;
number.pop_back();
}
else if ( number[i-1].first > number[i-1].ends && number[i].first > number[i].ends )// de droite à gauche
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number[i].length = number[i].first -number[i].ends;
number.pop_back();
}
}//for
}
int getFirst (std::vector<Layer> &number, int i)
{
return number[i].first;
}
int getEnds (std::vector<Layer> &number, int i)
{
return number[i].ends;
}
int getLength ()
{
return length;
}
private :
int first;
int ends;
int length;
};
class Counter /* class qui compte les superposition de couche de peinture */
{
public :
int compareAndLayerCounter (Layer &layers, std::vector<Layer> &number, int &entryNumber)
{
int counter = 0;
int maxCounter = 0;
if ( number.size() == 1)
{
maxCounter = 1;
}
else
{
for ( int i=0; i<entryNumber-1; ++i)
{
if (layers.getFirst(number, i) != layers.getEnds(number, i)) // Si pas 1,1 par exemple
{
counter = 0;
for (int j=0; j<entryNumber-1; ++j)
{
if ( (layers.getFirst(number, i) >= layers.getFirst(number, j) && layers.getEnds(number, i) <= layers.getEnds(number, j) && layers.getFirst(number, i) <= layers.getEnds(number, j) ) // 25,24 comparer avec 20,30 par exemple
||
(layers.getFirst(number, i) >= layers.getEnds(number, j) && layers.getEnds(number, i) <= layers.getFirst(number, j) && layers.getFirst(number, i) <= layers.getFirst(number, j)) ) // 25,24 comparer avec 30,20 par exemple
{
++counter;
}
}//for j
if ( counter > maxCounter )
{
maxCounter = counter;
}
}//if
}//for i
}//else
return maxCounter;
}
// Surcharge pour les longues entrées
int compareAndLayerCounter (Layer &layers, std::vector<Layer> &number, int &entryNumber, int &entryNumberBis)
{
int counter = 0;
int maxCounter = 0;
if ( number.size() == 1)
{
maxCounter = 1;
}
else
{
for ( int i=0; i<600; ++i)
{
if (layers.getFirst(number, i) != layers.getEnds(number, i)) // Si pas 1,1 par exemple
{
counter = 0;
for (int j=0; j<entryNumber-1; ++j)
{
if ( (layers.getFirst(number, i) >= layers.getFirst(number, j) && layers.getEnds(number, i) <= layers.getEnds(number, j) && layers.getFirst(number, i) <= layers.getEnds(number, j) ) // 25,24 comparer avec 20,30 par exemple
||
(layers.getFirst(number, i) >= layers.getEnds(number, j) && layers.getEnds(number, i) <= layers.getFirst(number, j) && layers.getFirst(number, i) <= layers.getFirst(number, j)) ) // 25,24 comparer avec 30,20 par exemple
{
++counter;
}
}//for j
if ( counter > maxCounter )
{
maxCounter = counter;
}
}//if
++i; }//for i
}//else
return maxCounter;
}
};
bool compareLength (Layer one, Layer two) /* Fonction qui compare les longueurs d'intervalles de la plus petite à la plus grande */
{
return one.getLength() < two.getLength();
}
int main()
{
int entryNumber = 0;
Layer layers;
Counter counters;
std::cin >> entryNumber;
std::vector<Layer> number (entryNumber-1, Layer() );
layers.inputEntry(number, entryNumber); // lecture des entrées
std::stable_sort(number.begin(), number.begin()+entryNumber-1, compareLength); // tri du plus petit interval au plus grand
if (entryNumber<=100)
{
std::cout << counters.compareAndLayerCounter(layers, number, entryNumber); // compter && afficher le maximum de couche de peinture superposée au même endroit
}
else
{
std::cout << counters.compareAndLayerCounter(layers, number, entryNumber, entryNumber); // Pour les grande entrée
}
return 0;
}
En fait, pour l'indentation, l'idée est que tout ce qui fait partie d'un "bloc d'instructions", tout ce qui se trouve entre une paire d'accolades (ou de parenthèses ou de quoi que ce soit), soit au même niveau (pour ce qui concerne le bloc d'instructions) et "décalé" par rapport au blocs d'instructions parent.
pour un test "vrai faux", avec "quelque chose" à faire si le test donne faux, cela pourrait ressembler à quelque chose comme
le tout, avec un nombre d'espaces susceptible de varier, cela n'a pas *** énormément *** d'importance
Remarque juste que le else (et donc, un éventuel else if) est aligné avec le if auquel il se rapporte
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
D’accord je comprend mieux maintenant. Du coup mon code bien indenté devrait plutôter ressembler à ceci :
#include <iostream>
#include <algorithm>
#include <vector>
class Layer
{ /* class qui lit les entrées && calcul "length" && réduit les entrées du genre "5,4,3,2 en 5,2" */
public :
void inputEntry (std::vector<Layer> &number, int &entryNumber)
{
std::cin >> number[0].first; // Première && deuxième entrée
std::cin >> number[0].ends;
// Calcul de la longueur de l'interval pour les trier par la suite
if ( number[0].first>number[0].ends )
{
number[0].length = number[0].first -number[0].ends;
}
else
{
number[0].length = number[0].ends -number[0].first;
}
for (int i=1; i<entryNumber-1; ++i)
{ // A partir de la troisième entrée
number[i].first = number[i-1].ends;
std::cin >> number[i].ends;
if ( number[i].first>number[i].ends )
{
number[i].length = number[i].first -number[i].ends;
}
else
{
number[i].length = number[i].ends -number[i].first;
}
// si first < ends on va de G à D si first < ends on va toujours de G à D
if ( number[i-1].first < number[i-1].ends && number[i].first < number[i].ends )// de gauche à droite
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number[i].length = number[i].ends -number[i].first;
number.pop_back();
}
else if ( number[i-1].first > number[i-1].ends && number[i].first > number[i].ends )// de droite à gauche
{
number[i-1].ends = number[i].ends;
--i;
--entryNumber;
number[i].length = number[i].first -number[i].ends;
number.pop_back();
}
}//for
}
int getFirst (std::vector<Layer> &number, int i)
{
return number[i].first;
}
int getEnds (std::vector<Layer> &number, int i)
{
return number[i].ends;
}
int getLength ()
{
return length;
}
private :
int first;
int ends;
int length;
};
class Counter /* class qui compte les superposition de couche de peinture */
{
public :
int compareAndLayerCounter (Layer &layers, std::vector<Layer> &number, int &entryNumber)
{
int counter = 0;
int maxCounter = 0;
if ( number.size() == 1)
{
maxCounter = 1;
}
else
{
for ( int i=0; i<entryNumber-1; ++i)
{
if (layers.getFirst(number, i) != layers.getEnds(number, i)) // Si pas 1,1 par exemple
{
counter = 0;
for (int j=0; j<entryNumber-1; ++j)
{
if ( (layers.getFirst(number, i) >= layers.getFirst(number, j) && layers.getEnds(number, i) <= layers.getEnds(number, j) && layers.getFirst(number, i) <= layers.getEnds(number, j) ) // 25,24 comparer avec 20,30 par exemple
||
(layers.getFirst(number, i) >= layers.getEnds(number, j) && layers.getEnds(number, i) <= layers.getFirst(number, j) && layers.getFirst(number, i) <= layers.getFirst(number, j)) ) // 25,24 comparer avec 30,20 par exemple
{
++counter;
}
}
if ( counter > maxCounter )
{
maxCounter = counter;
}
}//if
}
}//else
return maxCounter;
}
};
bool compareLength (Layer one, Layer two) /* Fonction qui compare les longueurs d'intervalles de la plus petite à la plus grande */
{
return one.getLength() < two.getLength();
}
int main()
{
int entryNumber = 0;
Layer layers;
Counter counters;
std::cin >> entryNumber;
std::vector<Layer> number (entryNumber-1, Layer() );
layers.inputEntry(number, entryNumber); // lecture des entrées
std::stable_sort(number.begin(), number.begin()+entryNumber-1, compareLength); // tri du plus petit interval au plus grand
std::cout << counters.compareAndLayerCounter(layers, number, entryNumber); // compter && afficher le maximum de couche de peinture superposée au même endroit
return 0;
}
les lignes 28, 32, 37 et 45 devraient être alignées avec les lignes 25 et 26
la ligne 43 n'est pas correctement alignée avec la ligne 38 (les lignes 46 et 53 ne seront, du coup, plus alignées non plus)
de manière générale, avoir une double indentation (avant l'accolade ouvrante et avant les instructions du bloc), ca fait beaucoup d'indentation pour pas grand chose, car ce qui se trouve entre l'accolade ouvrante et l'accolade fermante est destiné à faire "un tout"...
Au final, tu es relativement libre de choisir ta propre manière d'indenter ton code, le tout est d'arriver à trouver ton propre équilibre entre:
avoir un code "compact"pour lequel tu n'aie pas à jouer en permanence avec les ascenseurs et / ou la barre de défilement latérale et / ou la "pliure" du code pour arriver à le lire
avoir un code dans lequel il soit facile de retrouver quelle instruction va avec quelle autre
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
Merci beaucoup pour tout vos conseil, ça m'aide beaucoup pour progresser!
Ici j'avais fait une petite pause d'algoréa quand soudain, j'avais une idée en tête, du coup me revoila avec cette fois 80%, ça débloque l'exercice suivant mais ca m'intéresse pas, je veux les 100%; Je cherche encore un moyen efficace de passer moins dans la double boucle for, j'ai eu quelque idée mais c'est toujours pas suffisant, l'idéal ce serais de savoir comment trouver l'intervalle la plus susceptible d'être la bonne, j'ai d'abbord pensé " bah c'est sans doute dans les plus petites" niette, j'ai trier du plus petit au plus grand et commencer par les plus petites intervalles, je pouvais passer max 2000 fois dans ma double boucle for sans dépasser les 100ms, mais c'est loin d'être assez; J'ai tenté de faire la moyenne des intervalles et calculer la longueur de chaque intervalles pour créer une condition " if " qui réduirait le nombre de passage en fonction du plus petit intervalle, de la plus grande et de la moyenne( j'ai essayer plusieurs façon ca serais trop long à détailler mais je dépasse toujours, il doit y avoir un autre moyen plus logique que ces méthodes bizarre que j'ai employée; Les 4 test qui dépasse les 100ms sont le 12,13,14,15, tout le reste est validé;
Edit: je sait que pour les attribut normalement c'est "m_nomAttribut" mais pour algoréa j'avais pas trop envie
Au passage l'exercice suivant c'est juste un truc de fou, j'ai été perdu rien que dans l'énoncé déjà lol;
voici le code à 80% :
#include <iostream>
#include <algorithm>
#include <vector>
class Layer
{ /* class avec une méthode qui lit les entrées et crée les intervalles [5,3] [3,4] [4,3] ...
&& réduit les entrées du genre "[5,4] [4,3] [3,2] en [5,2]"
&& calcule length, minLength, maxLength, average (afin d'essaier de passer moins dans la boucle plus bas)*/
public :
void inputEntry (std::vector<Layer> &interval, int &entryNumber)
{
std::cin >> interval[0].first; // Première && deuxième entrée
std::cin >> interval[0].ends;
// Calcul de la longueur de l'interval pour les trier par la suite
if ( interval[0].first>interval[0].ends )
{
interval[0].length = interval[0].first -interval[0].ends;
}
else
{
interval[0].length = interval[0].ends -interval[0].first;
}
minLength = interval[0].length;
maxLength = 0;
average = 0;
average += interval[0].length;
for (int i=1; i<entryNumber-1; ++i)
{ // A partir de la troisième entrée
interval[i].first = interval[i-1].ends;
std::cin >> interval[i].ends;
if ( interval[i].first>interval[i].ends )
{
interval[i].length = interval[i].first -interval[i].ends; // Calcul de la longueur de l'intervalle
}
else
{
interval[i].length = interval[i].ends -interval[i].first;
}
// si first < ends on va de G à D si first < ends on va toujours de G à D
if ( interval[i-1].first < interval[i-1].ends && interval[i].first < interval[i].ends )// de gauche à droite
{
interval[i-1].ends = interval[i].ends;
--i;
--entryNumber;
interval[i].length = interval[i].ends -interval[i].first;
interval.pop_back();
}
else if ( interval[i-1].first > interval[i-1].ends && interval[i].first > interval[i].ends )// de droite à gauche
{
interval[i-1].ends = interval[i].ends;
--i;
--entryNumber;
interval[i].length = interval[i].first -interval[i].ends;
interval.pop_back();
}
if ( interval[i].length > maxLength )
{
maxLength = interval[i].length;
}
if ( minLength > interval[i].length )
{
minLength = interval[i].length;
}
average += interval[i].length;
}//for
average /= entryNumber;
}
int getFirst ()
{
return first;
}
int getEnds ()
{
return ends;
}
int getLength ()
{
return length;
}
int getMaxLength ()
{
return maxLength;
}
int getMinLength ()
{
return minLength;
}
int getAverage ()
{
return average;
}
private :
int first;
int ends;
int length;
int maxLength;
int minLength;
int average;
};
class Counter /* class avec une méthode qui compte les superposition de couche de peinture */
{
public :
int compareAndLayerCounter (std::vector<Layer> &interval, int &entryNumber)
{
int counter = 0;
int maxCounter = 0;
for ( int i=0; i<entryNumber-1; ++i)
{
if (interval[i].getFirst() != interval[i].getEnds()) // Si pas 1,1 par exemple
{
counter = 0;
for (int j=0; j<entryNumber-1; ++j)
{
if ( (interval[i].getFirst() >= interval[j].getFirst() && interval[i].getEnds() <= interval[j].getEnds() && interval[i].getFirst() <= interval[j].getEnds() ) // 25,24 comparer avec 20,30 par exemple
||
(interval[i].getFirst() >= interval[j].getEnds() && interval[i].getEnds() <= interval[j].getFirst() && interval[i].getFirst() <= interval[j].getFirst()) ) // 25,24 comparer avec 30,20 par exemple
{
++counter;
}
}//for j
if ( counter > maxCounter )
{
maxCounter = counter;
}
}
}//for i
return maxCounter;
}
int longCompareAndLayerCounter (std::vector<Layer> &interval, int &entryNumber, Layer layers)
{
int counter = 0;
int maxCounter = 0;
int max = layers.getMaxLength() - layers.getMinLength();
max /= 2;
for ( int i=0; i<entryNumber-1; ++i) // boucle pour les entrées de 20.000 avec condition pour tentez de faire moins de passage
{
if ( interval[i].getLength() >= layers.getMinLength() && interval[i].getLength() <= interval[i].getLength()+ max )
{
if (interval[i].getFirst() != interval[i].getEnds()) // Si pas 1,1 par exemple
{
counter = 0;
for (int j=0; j<entryNumber-1; ++j)
{
if ( (interval[i].getFirst() >= interval[j].getFirst() && interval[i].getEnds() <= interval[j].getEnds() && interval[i].getFirst() <= interval[j].getEnds() ) // 25,24 comparer avec 20,30 par exemple
||
(interval[i].getFirst() >= interval[j].getEnds() && interval[i].getEnds() <= interval[j].getFirst() && interval[i].getFirst() <= interval[j].getFirst()) ) // 25,24 comparer avec 30,20 par exemple
{
++counter;
}
}//for j
if ( counter > maxCounter )
{
maxCounter = counter;
}
}
}//if<
}//for i
return maxCounter;
}
};
bool intervalComparatorFIRSTends (std::vector<Layer> &interval, int &entryNumber) // exemple : 11 1 12 2 13 3 14 4 ...
{
for ( int i=0; ( entryNumber>2 && i<entryNumber-1 && interval[i].getFirst()<interval[0].getEnds() )
|| ( entryNumber>2 && i<entryNumber-1 && interval[i].getEnds() <interval[0].getEnds() ); ++i)
{
if ( i == entryNumber-2)
{
return true;
}
}
return false;
}
bool intervalComparatorENDSfirst (std::vector<Layer> &interval, int &entryNumber) // exemple : 1 11 2 12 3 13 4 14 ...
{
for ( int i=0; ( entryNumber>2 && i<entryNumber-1 && interval[i].getEnds() <interval[0].getFirst())
|| ( entryNumber>2 && i<entryNumber-1 && interval[i].getFirst()<interval[0].getFirst()); ++i)
{
if ( i == entryNumber-2)
{
return true;
}
}
return false;
}
int main()
{
int entryNumber = 0;
Layer layers;
Counter counters;
std::cin >> entryNumber;
std::vector<Layer> interval (entryNumber-1);
layers.inputEntry(interval, entryNumber); // lecture des entrées
// compter && afficher le maximum de couche de peinture superposée au même endroit
if (entryNumber <= 100)
{
std::cout << counters.compareAndLayerCounter(interval, entryNumber);
}
else
{
if ( intervalComparatorFIRSTends(interval, entryNumber))
{
std::cout << entryNumber-1;
}
else if ( intervalComparatorENDSfirst(interval, entryNumber))
{
std::cout << entryNumber-1;
}
else
{
std::cout << counters.longCompareAndLayerCounter(interval, entryNumber, layers);
}
}
return 0;
}
concernant les histoires de versions de c++ acceptées, Algorea n'est pas un concours de programmation destiné aux développeurs, c'est un concours d'algorithmique destiné aux collégiens et lycéens. Il n'est donc en principe nul besoin d'une connaissance approfondie d'un langage pour résoudre les problèmes.
Je me suis confronté aux couches de peinture car mon fils participe, et comme beaucoup, bloqué à 55% ( temps de limite dépassé sur le reste ), je cherchais si le sujet n'avait pas été discuté. Donc merci à Michas pour la discussion.
Finalement, c'est après avoir cogité en vain et être allé me promener au bord du lac pour jeter des morceaux de pain aux canards, que l'algorithme salvateur m'est venu. Codé en python, il prend 24 lignes et obtient 100%.
Le voici
- initialiser deux tableaux remplis de 0 de nbPositions+1 éléments, nbCouchesEnPlusSiApres et nbCouchesEnMoinsSiApres
- parcourir les entrées, au coup i, incrémenter l'élément i de nbCouchesEnPlusSiApres de l'extrémité la plus petite et incrémenter l'élément i de nbCouchesEnMoinsSiApres de l'extrémité la plus grande
-initialiser nbmax, totalCouchesEnPlus et totalCouchesEnmoins à 0
- parcourir de 0 à nbPositions : incrémenter totalCouchesEnPlus avec nbCouchesEnPlusSiApres[i], idem pour moins. Le nombre de couches est
totalCouchesEnPlus-totalCouchesEnMoins, si c'est supérieur à nbmax, nbmax reçoit la valeur.
× 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.
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"; }
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"; }
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"; }
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"; }
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"; }