Discussion :

[AnnaConda]

Je voudrais reçcevoir un peu d'aide pour un exercice. Voici l'énoncé :

Ce que doit faire votre programme :

nbGrenouilles numérotées de 1 à nbGrenouilles sont placées sur une ligne de départ. À chaque tour, on vous indique le numéro de la seule grenouille qui va sauter lors de ce tour, et la distance qu'elle va parcourir en direction de la ligne d'arrivée.

Écrivez un programme qui détermine laquelle des grenouilles a été strictement en tête de la course au début du plus grand nombre de tours. Notez que comme on s'intéresse à qui est en tête au début de chaque tour, le bond du dernier tour ne sert à rien car même si la grenouille concernée passe en tête, la course est finie (il est purement honorifique selon la tradition algoréenne).
LIMITES DE TEMPS ET DE MEMOIRE (Langage : C)

Temps : 1s sur une machine à 1Ghz.
Mémoire : 16000 Ko.
CONTRAINTES

1 <= nbGrenouilles <= 100
1 <= nbTours <= 1000
1 <= distanceSauti <= 100

ENTRÉE

La première ligne de l'entrée contient un entier, le nombre de grenouilles nbGrenouilles qui participent à la course. Les grenouilles sont numérotées de 1 à nbGrenouilles.

La deuxième ligne de l'entrée contient le nombre de tours nbTours de la course.

Chacune des nbTours lignes suivantes décrit un tour par deux entiers séparés par un espace. Le premier entier est le numéro de la grenouille qui saute à ce tour, et le deuxième, est la distance parcourue par la grenouille lors de ce saut.
SORTIE

Vous devez afficher un entier sur la sortie : le numéro de la grenouille qui a été strictement en tête au début du plus grand nombre de tours. En cas d'égalité entre plusieurs grenouilles, choisissez celle dont le numéro est le plus petit.
EXEMPLE

entrée :

4
6
2 2
1 2
3 3
4 1
2 2
3 1

sortie :

2

COMMENTAIRES

Pour l'exemple proposé, indiquons la distance totale parcourue par chaque grenouille au début de chaque tour :

Grenouille : 1 2 3 4
Tour 1 : 0 0 0 0
Tour 2 : 0 2 0 0
Tour 3 : 2 2 0 0
Tour 4 : 2 2 3 0
Tour 5 : 2 2 3 1
Tour 6 : 2 4 3 1

La grenouille 1 est restée 0 tour en tête, la seconde 2 (les tours 2 et 6), la troisième 2 (les tours 4 et 5) et la quatrième 0. C'est donc la grenouille 2 qui remporte la victoire.

J'ai codé une solution en C, mais elle ne passe que 11 tests sur 20. La voici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
int max (int *grenouilles, int t)
{
   int maximum = 1, prec = grenouilles[1];
   for (int i = 2; i <= t; i++){
      if (grenouilles[i] > prec)
         maximum = i;
      prec = grenouilles[i];
   }
   return maximum;
}
 
int main ()
{
   int nbg, nbt, num, saut, preums, prec = 0, valPrec = 0;
   bool egal = false;
 
   scanf("%d\n%d", &nbg, &nbt);
 
   int *grenouilles = NULL, *tete = NULL;
   grenouilles = malloc(sizeof(int) * (nbg+1));
   tete = malloc(sizeof(int) * (nbg+1));
 
   for (int i = 1; i < nbt; i++){
      scanf("%d %d\n", &num, &saut);
      grenouilles[num] += saut;
 
      if(grenouilles[num] > valPrec){
         tete[num]++;
         prec = num;
         valPrec = grenouilles[num];
         egal = false;
      }
      else if (grenouilles[num] == valPrec)
         egal = true;
      if (!egal){
         if (valPrec > grenouilles[num]){
            tete[prec]++;
         }
      }
   }
 
   preums = max(tete, nbg);
 
   printf("%d", preums);
 
   free(grenouilles);
   free(tete);
   grenouilles = NULL;
   tete = NULL;
 
   return 0;
}

Vous n'auriez pas une idée de l'erreur commise dans ce code ?

[orfix]

Ce qui me saute aux yeux c'est les deux tableaux grenouilles[] et tete[] qui ne sont jamais initialisés, c'est pourquoi je te suggère l'utilisation de calloc() et non malloc():

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
   grenouilles = calloc(nbg+1, sizeof(int));
   tete = calloc(nbg+1, sizeof(int));

Sinon je ne vois pas trop l'utilité de ta variable bool egal, tu peux très bien l'éliminer je pense:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
   for (i = 1; i < nbt; i++){
	   scanf("%d %d\n", &num, &saut);
	   grenouilles[num] += saut;
 
	   if(grenouilles[num] > valPrec){
		   tete[num]++;
		   prec = num;
		   valPrec = grenouilles[num];
	   } 
	   else if (grenouilles[num] < valPrec) {
		   tete[prec]++;
	   }
   }

Si ça ne fonctionne toujours pas, c'est que ton algorithme est faux, je te conseille d'écrire une fonction pour afficher grenouilles[] et tete[] à chaque tour (ou sinon utiliser un debugger) pour comprendre ce qui se passe au juste.

[AnnaConda]

Merci pour l'idée du calloc(). Pour le booléen, je peux t'assurer qu'il est utile (le flemme d'expliquer pourquoi). Et pour ta technique de debug, j'ai voulu essayer, mais l'entrée que le site envoie à mon programme contient 175 tours... Un peu hard de tout parcourir.

[Trademark]

Salut,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(valPrec > grenouilles[num])

C'est un supérieur strict du coup ton égal sert à rien vu que si valPrec == grenouilles[num] ça passera de toutes façons pas la dedans.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
int max (int *grenouilles, int t)
{
   int maximum = 1;
   prec = grenouilles[1];
   for (int i = 2; i <= t; i++){
      if (grenouilles[i] > prec)
         maximum = i;
      prec = grenouilles[i]; // <------- Doit être dans le if
   }
   return maximum;
}

En fait c'est une "bête" recherche de maximum dans un tableau que tu fais. Du coup il ne faut pas que tu retiennes le précédent à chaque fois mais le meilleure précédent ! Du coup c'est grenouilles[maximum], pas besoin de variable prec.

[Chatanga]

Si on fait abstraction de la non initialisation des tableaux 'grenouilles' et 'tete' et de la gestion des indices un brin discutable, la source du problème réside probablement dans le 'egal' : les sauts sur place (d’une distance nulle) et la présence de plusieurs grenouilles au même endroit (pas seulement les deux dernières ayant sauté) sont mal gérés.

Par exemple :

3
6
3 50
2 50
1 50
1 100
1 100
1 100

En récrivant et corrigeant 'max' qui comporte aussi une erreur, ce sera plus simple pour tester :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int max (int *grenouilles, int t)
{
   int maximum = 1, prec = grenouilles[1];
   for (int i = 1; i <= t; i++){
      printf("%d -> %d\n", i, grenouilles[i]);
   }
   for (int i = 2; i <= t; i++){
      if (grenouilles[i] > prec) {
         maximum = i;
         prec = grenouilles[i];
      }
   }
   return maximum;
}

[AnnaConda]

Ah oui, c'est la fonction "max" qui avait des ratés, finalement...

Merci pour vos réponses !

[Bktero]

Si le problème est résolu, merci de quitter sur le bouton en bas de la page.