Prologin 2016

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut à tous,

La qualification du concours Prologin touche à sa fin (le 3 janvier) et la prochaine étape se déroulera en février 2016 dans les grandes villes de France.

Participez-vous à ce concours ? Venant de Lyon, j'aimerais savoir si il y a des Agrumes parmi nous qui aient demandé l'ISEG de Lyon pour passer la demi-finale.

Je vous écoute !

hello, world !

+0 -0

ThuleMalta : accroche toi, c'est une superbe expérience, et les premières phases de sélection sont très souples !

Je participe aussi, en ocaml ! C'est ma dernière année en tant que participant donc il faut au moins que j'aille jusqu'au bout une fois. :p Par contre je serais certainement plus du côté de Paris.

+0 -0

Bonne idée que d'encourager les gens a venir ! ThuleMalta, je ne pense pas que les connaissances en math soient vraiment importantes. Je me suis qualifié en 4em et 3em pour la finale, c'est donc que ça doit suffire ce niveau ! Prologin c'est moins des math que de l'algorithmie, ce qui peut s'apprendre totalement indépendamment de l’école (via wikipedia pour les algos, des tutoriels, et la quantité impressionnante d'exos sur le site france-ioi) Et 3 sur 5 c'est pas mal. En fait le deux autres nécessitent d'avoir déjà abordé ce type de problèmes…

+0 -0

Salut à tous,

La qualification du concours Prologin touche à sa fin (le 3 janvier) et la prochaine étape se déroulera en février 2016 dans les grandes villes de France.

Croal

Arf ! Me dis pas ça, j'ai pas encore commencé ! x(

Prologin est vraiment une super expérience. Je n'en garde que de bons souvenirs ^^

Pour avoir été en finales, c'est vraiment une expérience que je n'oublierais pas ! Pour dire, ce que j'y ai appris me sert actuellement dans mon parcourt universitaire (Bac+3) !

Cependant, le concours à tout de même un certain niveau.

Édité par ache

+0 -0

L'algorithmie, selon moi, c'est résoudre des problèmes mathématiques grâce à l'informatique. Quand je dis que je n'ai pas le niveau pour les exercices 4 et 5, c'est que je ne sais même pas par ou commencer.
@ache Faire des recherches sur Internet ça n'a pas grand intérêt à mon avis, le but c'est de trouver par soi-même. Être sélectionné en cherchant sur Internet pour ensuite ne savoir rien faire une fois arrivée la demi-finale, c'est pire que de ne réussir qu'une partie des exercices soi-même et n'être pas sélectionné (selon moi).

Après, si 3 exercices suffisent à aller en demi-finale, je croise les doigts. :)

ThuleMalta - C#, PHP, Python/Django, Unity3D. mon blog

+0 -0

@ache Faire des recherches sur Internet ça n'a pas grand intérêt à mon avis, le but c'est de trouver par soi-même. Être sélectionné en cherchant sur Internet pour ensuite ne savoir rien faire une fois arrivée la demi-finale, c'est pire que de ne réussir qu'une partie des exercices soi-même et n'être pas sélectionné (selon moi).

Après, si 3 exercices suffisent à aller en demi-finale, je croise les doigts. :)

ThuleMalta

Pourtant, c'est dans la recherche que tu trouveras le plus de ressources aptes à pouvoir t'aider à préparer les demi-finales … Curieux non ?

Il faut être capable de se dire que l'on ne réinventera pas tous. Que des gens plus intelligents (ou pas d'ailleurs, ça n'a pas d'importance) que nous on déjà bien étudier certains problèmes et qu'ainsi comprendre leurs démarches nous apporte beaucoup.

Pour dire, le dernier exercice de qualification de l'édition 2012, relaxation En fait, pour bien comprendre le problème, il faut allez très loin.

Certains l'on fait avec de la programmation dynamique. À cette époque, je ne connaissais pas la programmation dynamique. J'étais incapable de la même en œuvre. C'est à Prologin justement que j'ai appris. Mais pour m'y qualifié, j'ai utilisé un algo peu connu. Imagine l'effort que ça a été pour étudier ce problème dans les détailles afin de coder l'algo issue de cet article.

Du coup, ben le problème du rendu de monnaie, je le connais bien maintenant ^^"

Je m’arrête avec un dernier exemple.

Cette année j'ai à coder un algorithme en 2 phases de Kociemba … Le gars qui a prouvé que le nombre de dieu du rubik's cube était 20. Son algorithme, impossible pour moi de le coder. Mais par-contre, la méthode, je l'ai bien comprise. Et si jamais un jour je repère un modèle identique dans un problème que je veux résoudre, je pourrais appliqué Kociemba à ce problème.

Idem pour l'algorithme de recherche KMP, l'algorithme de Borůvka, …

Édité par ache

+0 -0

D'autant plus que pour les algorithmes 4 et 5, ce sont des algorithmes qu'on rencontre dans beaucoup de problèmes courants.

Certains font prologin avec le bagage d'une classe préparatoire, et 5 ans passés à chercher de plus que toi. Pourquoi n'aurais-tu pas le droit de chercher toi aussi ? C'est l'un des meilleurs entrainements pour progresser efficacement. ;)

+0 -0

Bonsoir ;-) !

C'est ma première participation (je suis en 1eS), et comme @ThuleMalta j'avoue que je bloque vraiment sur l'exercice n°4 tout particulièrement. Est-ce que l'un d'entre vous à une piste pour nous mettre sur la voie (il ne s'agit pas de donner la réponse bien sûr je trouve ça totalement inutile :p) ? J'ai déjà pensé à des algorithme comme Kruskal, la théorie des Graphes, mais j'ai lu qu'il fallait ici utiliser la programmation dynamique, que je n'ai jamais pratiquée …

Merci par avance pour vos réponses :)

A toi de chercher, de voir… Essaye de bien identifier le problème, c'est un problème classique. Ça semble effectivement ressembler a un graphe. Par contre, si tu as vu quelque part que c'était de la programmation dynamique… Que ça ne te bloque par pour autant ! Ne change pas de voie de recherche simplement en ayant vu ça. La programmation dynamique consiste, de base, simplement a retenir des calculs pour éviter de les refaire ensuite, et calculer des résultat en fonction des autres. Ce principe peut très bien être appliqué avec des algos de graphe ! (en fait c'est même très lié)

+0 -0
Auteur du sujet

Je bloque au troisième problème "La Prophétie". Si quelqu'un peut me donner un coup de main…

Voilà mon code :

 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
using namespace std;

int main()
{
    int volTempete, nbMontagnes;
    cin >> volTempete >> nbMontagnes;

    int altMontagnes[nbMontagnes];
    int altMinMontagne = 100000, altMaxMontagne = -100000;
    for(int iMont(0); iMont < nbMontagnes; iMont++)
    {
        cin >> altMontagnes[iMont];

        if(altMontagnes[iMont] < altMinMontagne)
            altMinMontagne = altMontagnes[iMont];

        if(altMontagnes[iMont] > altMaxMontagne)
            altMaxMontagne = altMontagnes[iMont];
    }

    int volTemporaire = -1;
    int altMer = altMinMontagne;
    int altTempete = altMaxMontagne + 1;

    while(volTemporaire != volTempete)
    {
        altTempete--;
        volTemporaire = 0;

        if(altTempete == altMer)
            break;

        for(int iMont(0); iMont < nbMontagnes; iMont++)
        {
            if(altTempete - altMontagnes[iMont] >= 0)
                volTemporaire += altTempete - altMontagnes[iMont];
        }
        //cout << "Vol : " << volTemporaire << endl;
    }

    cout << altTempete;
}

Édité par Croal

hello, world !

+0 -0

Personnellement, j'ai fait un algo qui augmente une variable niveau de la mer de 1 et qui compte le nombre de montagnes submergées à chaque itération.

Édité par ThuleMalta

ThuleMalta - C#, PHP, Python/Django, Unity3D. mon blog

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte