1. Accueil
  2. Tous les snippets
  3. Snippets C / C++ / C++.NET
  4. [prologin] qcm n° 5

[prologin] qcm n° 5

Soyez le premier à donner votre avis sur cette source.

Snippet vu 6 121 fois - Téléchargée 30 fois

Commenter

Contenu du snippet

C'est un algorithme qui permet de trouver le nombre de zéros du plus grand sous-tableau donné en entrée... (voir www.prologin.org pour plus d'information) !

Source / Exemple : 


#include <iostream>
using namespace std;

int tableau[1024][1024];

int bigRect(int l, int c)
{
  int x = 0, y, i, j;
  i = c + 1; j = 1; l++;
  do{
     i--;
     if(tableau[i][j]==1)x = 0;
     else x++;
     tableau[i][j] = x;
     if(i == 1){x = 0; j++; i = c + 1;}
  }while(j <= l);
  l--;
  //Il ne  me reste que 4 secondes !
  int q, s, d, f, res;
  int max = tableau[1][1];
  for(q = 1; q < l; q++)
  {
     for(s = 1; s < c; s++)
     {
        if(q  > 1 && tableau[s][q-1] >= tableau[s][q])
        {
           if(tableau[s][q]+s-1 == c)s = c - 1;
           else s += tableau[s][q];
           goto suite;
        }
        if(tableau[s][q] > 1)
        {
           for(d = tableau[s][q]; d > 1; d--)
           {
              for(f = q; f <= l; f++)
              {
                 if(tableau[s][f] >= d){if((res=d*(f-q+1)) > max)max = res;}
                 else if(tableau[s][f] < 2 ||(f == l && tableau[s][q]+s-1 == c))goto suite;
                 else break;
              }
           }
        }
suite:;
     }
  }
  return max;
}

int main()
{
  int l, c, L, C;
  cin >> l >> c;
  for(L = 1; L <= l; L++)
     for(C = 1; C <= c; C++)
        cin >> tableau[C][L];
  cout << bigRect(l, c);
  return 0;
}

Conclusion :


Malheureusement cette source est trop lente pour passer les 10 tests...
Si vous trouvez plus rapide, je vous en serais reconnaissant de me faire parvenir votre idée !!

Merci

A voir également

Ajouter un commentaire Commentaires
Signaler
Messages postés
10
Date d'inscription
mardi 6 mai 2003
Statut
Membre
Dernière intervention
16 mars 2004
Alle encore un petit effort a tous les participants du futur prologin! Travaillez vos algos ca vaut le coup, l'ambiance de la finale est terrible. malheureusment cette annee ca va etre impossible pour moi a cause des concours d'ecoles et apres je serais trop vieux.
Sinon pour trouver des idees je pense que tu vas devoir reflechir seul car ca serait un peu injuste envers les autres candidats sinon (ceci dit pour les questionnaires a la maison il est dur de verifier si le candidat a travailler seul mais ca se voit vite avec les epreuves de demi-finale)

Bonne chance!
Signaler
Messages postés
2368
Date d'inscription
mardi 17 avril 2001
Statut
Modérateur
Dernière intervention
26 décembre 2007
 20
si tu connais pas les pointeurs la suite va être difficile pour toi.

va sur commentcamarche.net ou www.developpez.com dans la rubriques cours , et brieffe toi rapidement sur le comment du pourquoi des pointeurs , ca te sera fort utile pour la suite du prologin !
Signaler
Messages postés
102
Date d'inscription
vendredi 22 février 2002
Statut
Membre
Dernière intervention
22 décembre 2003
Thearon => Je suis désolés de l'avoir posté si tôt mais je ne pense pas qu'elle ne serve-t-à grand chose, car elle ne passe que 6 tests sur 10 !!

BruNews => Qu'est ce que vous voulez dire par : "travailles avec des pointeurs" ?? Je m'en sert comment et pour quoi ??

Merci
Signaler
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 29
2 appels de fonction dans une triple boucle, mortel pour les performances, faut faire en interne.
Vire aussi les indexations et travaille avec des pointeurs.
Signaler
Messages postés
202
Date d'inscription
vendredi 6 juillet 2001
Statut
Membre
Dernière intervention
31 octobre 2007
J'ai également fais les algo pour prologin (malheureusement je ne passe que 8 tests sur 10) et je ne trouve pas tres correct de ta part de donner ton source avant la fin de l'inscription (1° janvier 2004 je crois).
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_RaZoR)