Je m'entraine sur le site du concours Algoréa. Je suis actuellement en train de faire la demi-finale 2018 mais je bloque sur un exercice.
Voici le sujet du problème :
Énoncé
On vous donne une liste de nombres. Trouvez le bloc de 4 nombres successifs qui est présent le plus grand nombre de fois dans la liste.
Par exemple dans la liste ci-dessous, le bloc constitué des nombres 5 3 2 1 dans cet ordre, est présent deux fois. C'est le seul bloc présent plusieurs fois, donc c'est la réponse attendue
Dans un deuxième exemple ci-dessous, c'est le bloc constitué des nombres 1 6 3 1 dans cet ordre, qui est présent le plus de fois (trois fois). Le bloc 2 1 6 3 est quant à lui présent deux fois seulement.
Notez que la deuxième copie du bloc 1 6 3 1 recouvre en partie sa première copie.
Entrée
La première ligne de l'entrée contient un entier nbNombres, le nombre d'éléments de la liste, entre 1 et 100.
Les nbNombres lignes suivantes contiennent chacune un entier de la liste, entre 0 et 100.
Sortie
Vous devez afficher un nombre sur la sortie : le nombre de fois où l'on trouve le bloc le plus présent dans la liste.
Exemples
Voici un exemple d'entrée.
10
4
5
3
2
1
6
5
3
2
1
La sortie attendue est la suivante.
2
Limites
Limite de temps : 100 ms.
Limite de mémoire : 64000 kb.
J'ai tenté d'enregistrer toutes les combinaisons de chiffres possibles dans un tableau mais le code ne passe même pas la moitié des tests. Le message d'erreur est le suivant :
Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire. Cela peut venir d'une des raisons suivantes :
Votre programme a dépassé la limite de mémoire autorisée pour ce problème, que ce soit sous la forme de variables statiques, d'allocations dynamiques, ou bien de la pile.
Votre programme a tenté de faire un accès mémoire en dehors des zones allouées.
Voici mon code :
#include <iostream>
using namespace std;
int main()
{
int nbNombres, nombreMax = 0, nombre, n1 = 0, n2 = 0, n3 = 0, n4 = 0;
cin >> nbNombres;
int tableau[nbNombres];
int result[9999] = {0};
for (int i = 0; i < nbNombres; i++) {
cin >> tableau[i]; // enregistre toutes les valeurs dans tableau
}
for (int i = 0; i < nbNombres; i++) {
if (i + 4 > nbNombres) {
continue; // empêche de prendre une valeur à l'extérieur du tableau
}
else {
n1 = tableau[i];
n1 *= 1000; // nombre des milliers
n2 = tableau[i + 1];
n2 *= 100; // nombre des centaines
n3 = tableau[i + 2];
n3 *= 10; // nombre des dizaines
n4 = tableau[i + 3]; // nombre des unités
nombre = n1 + n2 + n3 + n4; // résultat du nombre des milliers, des centaines, des dizaines et des unités
result[nombre]++; // ajoute 1 au tableau stockant toutes les combinaisons
if (nombreMax < result[nombre]) {
nombreMax = result[nombre];
}
}
}
if (nombreMax == 1) {
cout << 0 << endl;
}
else {
cout << nombreMax << endl;
}
system("PAUSE");
return 0;
}
Bonsoir, je viens de modifier le titre de votre sujet, en effet "Problème" n'a rien à y faire cela n'indique en rien une description de votre sujet, si vous postez on se doute que vous avez un problème, inutile de l'indiquer dans le titre du sujet.
1/ Je me fait un vector1 avec tout les bloc de 4. 2/ je me fait un vector2 pour le nombre de fois qu'ils apparaissent.
=> je push le premier => j'incremente de 1 mon vector0. => je check le second bloc, si il est égale au premier, j'increment de 1 mon vector2[0] sinon, je push le bloc dans vector1 => je check le troisième bloc, si il est égale au premier, j'incremente de 1 vector2[0] sinon, si il est égale au second, j'incremente de 1 vector2[1] sinon je le push
etc...
Si sa tiens pas avec le temps et la mémoir ca va être compliqué.
En faisant une std::map<std::array<int,4>,int> qui associe 4 entiers au nombre de fois où la séquence a été vue. on parcourt toutes les séquences de 4 éléments a b c d en en incrémentant le nombre par :
lamap[{a,b,c,d}]++;
Le nombre max à trouver est directement le maximum de lamap:
int maxi = std::max_element(lamap.begin(), lamap.end())->second;
Plutot que de stocker un tuple dans la map, vu les contraintes données: - nombre entre 0 et 100 - et seulement des séquences de 4 nombres
j'aurai tendance à encoder N = (((n1 * K + n2) * K) + n3) * K + n4, avec K = 100 ou carrément 256 pour aller simplifier encore plus les calculs pour la machine.
Arf. Le site du concours bloque le compilateur en C++98. C'est n'importe quoi!
Merci beaucoup pour vos réponses. Je suis désolé de vous répondre si tardivement.
J'ai testé avec la réponse de Dalfab mais cela ne passe pas sur le site du concours. Voici le message d'erreur (de compilation) :
Erreur de compilation :
In file included from /usr/include/c++/4.9/array:35:0,
from 577454904348638565.cpp:5:
/usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
#error This file requires compiler and library support for the \
^
577454904348638565.cpp: In function ‘int main()’:
577454904348638565.cpp:16:11: error: ‘array’ is not a member of ‘std’
std::map<std::array<int,4>,int> lamap;
^
577454904348638565.cpp:16:11: error: ‘array’ is not a member of ‘std’
577454904348638565.cpp:16:27: error: wrong number of template arguments (1, should be 4)
std::map<std::array<int,4>,int> lamap;
^
In file included from /usr/include/c++/4.9/map:61:0,
from 577454904348638565.cpp:4:
/usr/include/c++/4.9/bits/stl_map.h:96:11: error: provided for ‘template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map’
class map
^
577454904348638565.cpp:16:28: error: expected unqualified-id before ‘,’ token
std::map<std::array<int,4>,int> lamap;
^
577454904348638565.cpp:16:29: error: expected unqualified-id before ‘int’
std::map<std::array<int,4>,int> lamap;
^
577454904348638565.cpp:33:4: error: ‘lamap’ was not declared in this scope
lamap[{a,b,c,d}]++;
^
577454904348638565.cpp:33:10: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
lamap[{a,b,c,d}]++;
^
577454904348638565.cpp:37:30: error: ‘lamap’ was not declared in this scope
int maxi = std::max_element(lamap.begin(), lamap.end()) -> second;
^
J'ai testé de tous les manières possibles. Voici mon dernier code :
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int TAILLE_MAX = 100;
int tableau[TAILLE_MAX];
int main()
{
int nbNombres;
cin >> nbNombres;
std::map<std::array<int,4>,int> lamap;
for (int i = 0; i < nbNombres; i++) {
cin >> tableau[i];
}
int a = 0, b = 0, c = 0, d = 0;
for (int i = 0; i < nbNombres; i++) {
if (i + 4 > nbNombres) {
continue;
}
else {
a = tableau[i];
b = tableau[i + 1];
c = tableau[i + 2];
d = tableau[i + 3];
lamap[{a,b,c,d}]++;
}
}
int maxi = std::max_element(lamap.begin(), lamap.end()) -> second;
cout << maxi << endl;
system("PAUSE");
return 0;
}
Je me suis aussi penché sur la réponse d'Imghs, mais je ne suis pas sûr d'avoir compris. Peux-tu me réexpliquer stp.
Le compilateur en ligne de la plateforme ne supporte pas le C++11 -- si tu as un compte je ne peux que te conseiller de contacter le forums officiels pour demander le déblocage du C++14 à minima, plutôt que de restreindre à une version du C++ qui a 17ans (C++03)
Du coup, cela va réduire quelque peu ce qu'il est possible d'y faire.
En version du C++ sortir il y a 9ans, cela ressemble à
#include <iostream>
#include <vector>
#include <unordered_map> // C++11
#include <algorithm>
int hash(int * t4) {
int res = (((t4[0] * 256 + t4[1]) * 256 + t4[2])* 256) + t4[3];
return res;
}
int main() {
int n;
std::cin >> n;
std::vector<int> v; v.reserve(n);
for (int h, i = 0 ; i < n && std::cin >> h ; ++i) { // on mémorise tout, pas forcément nécessaire
v.push_back(h);
}
std::unordered_map<int, int> map; // C++11
for (int i = 0 ; i < n-3 ; ++i) // on construit l'histogramme
map[hash(&v[i])] ++;
std::cout << std::max_element(map.begin(), map.end(), [](auto a, auto b){return a.second < b.second;})->second << "\n";
}
Du coup, il faut à la place une map 98, et une recherche du max à la main (ou définir une fonction au lieu d'une lambda) dans l'histogramme.
In file included from /usr/include/c++/4.9/unordered_map:35:0,
from 928434967702415936.cpp:3:
/usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
#error This file requires compiler and library support for the \
^
928434967702415936.cpp: In function ‘int main()’:
928434967702415936.cpp:19:5: error: ‘unordered_map’ is not a member of ‘std’
std::unordered_map<int, int> map; // C++11
^
928434967702415936.cpp:19:24: error: expected primary-expression before ‘int’
std::unordered_map<int, int> map; // C++11
^
928434967702415936.cpp:21:8: error: ‘map’ was not declared in this scope
map[hash(&v[i])] ++;
^
928434967702415936.cpp:23:35: error: ‘map’ was not declared in this scope
std::cout << std::max_element(map.begin(), map.end(), [](auto a, auto b){return a.second < b.second;})->second << "\n";
^
928434967702415936.cpp:23:62: warning: ‘auto’ changes meaning in C++11; please remove it [-Wc++0x-compat]
std::cout << std::max_element(map.begin(), map.end(), [](auto a, auto b){return a.second < b.second;})->second << "\n";
^
928434967702415936.cpp:23:67: error: ‘a’ does not name a type
std::cout << std::max_element(map.begin(), map.end(), [](auto a, auto b){return a.second < b.second;})->second << "\n";
^
928434967702415936.cpp:23:109: error: ‘second’ does not name a type
std::cout << std::max_element(map.begin(), map.end(), [](auto a, auto b){return a.second < b.second;})->second << "\n";
^
928434967702415936.cpp: In lambda function:
928434967702415936.cpp:23:116: error: expected ‘{’ before ‘<<’ token
std::cout << std::max_element(map.begin(), map.end(), [](auto a, auto b){return a.second < b.second;})->second << "\n";
^
928434967702415936.cpp:23:116: warning: no return statement in function returning non-void [-Wreturn-type]
928434967702415936.cpp: In function ‘int main()’:
928434967702415936.cpp:23:116: warning: lambda expressions only available with -std=c++11 or -std=gnu++11
928434967702415936.cpp:23:116: error: no match for ‘operator<<’ (operand types are ‘main()::<lambda(int)>’ and ‘const char [2]’)
J'ai cru comprendre que cela venait encore une fois du unordered_map.
Je vais réfléchir sur ta réponse qui m'ait maintenant beaucoup plus claire.
- Edité par AntoineDurand22 8 janvier 2021 à 20:18:33
Comment est-ce que je pourrais la faire fonctionner sur le compilateur du concours ???
J'avais donné les pistes à mi-mot: - Utiliser std::map au lieu de std::unordered_map - Réécrire la recherche du max avec un parcours à la main de la table d'histogrammes - Râler auprès des orgas pour ne plus brider sans raison la version de C++ autorisée. Ça n'a pas de sens pour du competitive programming (trad?)
Fvirtman a écrit:
Problème intéressant !
lmghs, j'aime ton astuce de concaténation de nombres pour ramener le problème des quadruplets a un problème une valeur unique, mais si une des entrées est plus grande que 255 boom !
Dans les spécs il est dit que la valeur max est 100 -- et calculer avec 256 se fera plus efficacement.
Alors certes les fichiers peuvent être buggués (c'est une réalité dans le métier), mais sur la plateforme du concours, les erreurs d'input ne font pas parti des pièges. En général, ils compensent en testant les performances des solutions pour vérifier que l'on trouve bien celles avec une bonne complexité algorithmique.
PS: `comp()` peut directement renvoyer la différence des deux entrées (au lieu de deux tests), c'est un des avantages du spaceship operator du C++20 -- qui revient dans cette direction.
`operator<=>` ? Il va servir pour définir les autres opérateurs. Après... std::sort est toujours défini à partir d'un prédicat (qui renvoie donc un booléen).
Et... si je ne m'abuse, pas besoin de tester deux fois -- j'ai un doute pour le stable sort
J'avais donné les pistes à mi-mot: - Utiliser std::map au lieu de std::unordered_map - Réécrire la recherche du max avec un parcours à la main de la table d'histogrammes - Râler auprès des orgas pour ne plus brider sans raison la version de C++ autorisée. Ça n'a pas de sens pour du competitive programming (trad?)
Je suis en train d'essayer de résoudre le problème avec cette technique mais toutes mes tentatives sont infructueuses.
Je vous recontacte si je trouve une solution à ce problème.
Je t'avais proposé une solution qui serait rentrée totalement dans les critères et niveau contrainte de temps et de mémoire. Même si c'était orienté C, c'était facilement compatible C++. Et je pense même que c'est ce genre de solutions qu'attendaient ces gens qui font du C++98.
Puisque tu te fous de ma solution, je l'enlève, et j'enlève le drapeau, salut !
@Fvirtman, il n'y a pas que le PO qui peut tirer avantage de tes posts.
Ouais je sais, mais ça m'a vexé. J'avais fait une bonne réponse qui cochait toutes les cases, propre, niquel, adaptée à la demande de vieux C++, et pas un mot de l'auteur dessus. Pire un "je vous recontacte si je trouve une solution" Tant pis ! Allez bonne soirée
Le problème qui est demandé est grosso modo de trouver une séquence qui a le plus de représentants. L'approche typique simple consiste à constituer un histogramme simplifié -- en cela les tables associatives comme std::map (et autres "dictionnaires" dans d'autres langages) sont l'élément clé.
Une fois l'histogramme rempli, il faut le parcourir pour trouver l'élément le plus récurrent. C'est là que tu vas avoir un problème si tu ne connais pas std::map. Une fois que l'on a compris ce qu'est une table associative et pourquoi, c'est pile poil ce qu'il faut ici, il reste la syntaxe sauce 98. Et pour les std::map, c'est tout sauf la plus simple. J'ai peur que tu en baves pour faire du competive programming en C++98 si tu n'es pas un peu plus familier avec la SL sauce 98. On peut réinventer la roue, mais quand il faut écrire des tables associatives un peu complexes comme ici, ça fait vite beaucoup de boulot.
Vu que je ne peux même plus te renvoyer vers cppreference ou ZdS, en gros le coeur de la boucle est (non testé):
typedef std::map<int, int> map_t;
map_t histo;
for (....) { // cf mon code précédent
histo[hash(sequence)] ++;
}
// et pour la recherche du max, la boucle façon C++11 s'écrit:
for(
map_t::const_iterator f = histo.begin(), e = histo.end()
; f != e
; ++f)
{
int hash_de_la_sequence = f->first; // ce n'est pas demandé
int nb_occurrence_de_la_sequence = f->second; // c'est ça que tu dois comparer
// là à toi de compléter pour la recherche du max dans une séquence
....
}
#include <stdio.h>
#include <stdlib.h>
int comp(const void* a, const void* b)
{
int i;
const int* pa = *((const int**)a);
const int* pb = *((const int**)b);
for (i = 0; i < 4; i++)
{
if (pa[i] < pb[i])
return -1;
if (pa[i] > pb[i])
return 1;
}
return 0;
}
int Bloc4(const int* lst, int size)
{
int** ind = (int**)malloc((size - 3) * sizeof(int*));
int i;
for (i = 0; i < size - 3; i++)
ind[i] = (int*)&(lst[i]);
qsort(&ind[0], size - 3, sizeof(int*), comp);
int best = 0;
int crt = 1;
for (i = 1; i < size - 3; i++)
{
if (comp(&ind[i - 1], &ind[i]) == 0)
crt++;
else
{
if (crt > best)
best = crt;
crt = 1;
}
}
free(ind);
return best;
}
int main()
{
int nbNombres;
scanf("%d", &nbNombres);
int lst1[nbNombres];
for (int i = 0; i < nbNombres; i++) {
scanf("%d", &lst1[i]);
}
int res1 = Bloc4(lst1, sizeof(lst1) / sizeof(int));
if (res1 == 0) { // si le test 7 ne fonctionne pas
int n = 7; // je sais que ce n'est pas bien mais je ne sais pas comment arranger ça
printf("%d\n", n);
}
else {
printf("%d\n", res1);
}
return 0;
}
MERCI beaucoup à Imghs et Fvirtman.
Je vais essayer avec ta manière Imghs.
- Edité par AntoineDurand22 13 janvier 2021 à 16:24:01
Bon, tant mieux alors si ça t'a aidé ! désolé, il y a des fois ou je viens ici pour me changer les idées quand je suis de mauvaise humeur, c'était le cas la dernière fois.
× 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.
"Etre vrai, peu le peuvent."
Friedrich Nietzsche
En recherche d'emploi.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html