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 391 fois - Téléchargée 31 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
cooleric Messages postés 10 Date d'inscription mardi 6 mai 2003 Statut Membre Dernière intervention 16 mars 2004
30 déc. 2003 à 20:35
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!
TheSaib Messages postés 2368 Date d'inscription mardi 17 avril 2001 Statut Modérateur Dernière intervention 26 décembre 2007 22
23 déc. 2003 à 15:11
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 !
cs_RaZoR Messages postés 102 Date d'inscription vendredi 22 février 2002 Statut Membre Dernière intervention 22 décembre 2003
22 déc. 2003 à 11:52
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
BruNews Messages postés 21041 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 19
22 déc. 2003 à 11:35
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.
cs_Thaeron Messages postés 202 Date d'inscription vendredi 6 juillet 2001 Statut Membre Dernière intervention 31 octobre 2007
22 déc. 2003 à 11:29
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)