Demi finale à Paris I (Epita)

Je l'ai regardé rapidement, mais je pense que j'aurais donné un truc tout con du genre:

struct Candidat
{
int portee;
int x;
int y;
char statut; // 's' pour sourd , 'S' pour source, 'r' pour rien, 'd' pour double : sourd+source
};

Je ne vois pas vraiment pourquoi faire plus compliqué... Ou sinon ce serait peut être rajouter des données de précalculs...

Si tu abandonnes la question bonus sur les mégaphones, tu peux te représenter ça sous forme de graphe orienté, avec des arcs allant des candidats vers les candidats non-sourds à portée.

Ah donc c'est plutot une structure pour représente l'ensemble des candidats, c'est ca?

La question 3, hmm, en fait il suffirait pas de faire "return 2" ? Vu que tout les candidats sont liés et que la source peut être n'importe qui, ce ne sera pas 1 candidat qui devra être sourd (si c'est lui la source...) mais toujours 2 il me semble. Est-ce que ca vous semble logique ?

Aaaaah, donc il fallait peut-être prendre le "structure" au pied de la lettre ...
Bah ! Peu importe. C'est juste que je suis peut-être Hors Sujet tout du long !!! :D

*a essayé de répondre au sujet en Scheme *

@alex3er : Beh, la structure pour un candidat si tu veux un graphe ça peut être une liste d'adjacence, t'auras juste un :
class Candidat {
List list;
}
et ta liste contient tous les candidats non-sourds à portée de celui-ci.

Oki hihi lol \^\^

Tr@dem@rk > Hmm, nan, imagines une chaîne de plus de 30 candidats, chaque candidat n'étant à portée que ses voisins immédiats : si tu assourdis uniquement un des candidats en bout de chaîne, tu empêches le massacre, vu que tu seras obligé de le faire perdre en premier, mais que le temps d'atteindre la fin de la chaîne, plus de 30 minutes se seront écoulées, et la source n'aura plus perdu.

Hmm, remarque, je dis ça en considérant que tous les candidats doivent avoir perdu en même temps pour une hécatombe, mais c'est pas précisé, si c'est juste perdre à cause de la même source, c'est plus valable.

@ilod Justement, pendant l'épreuve il a été précisé que l'hécatombe suppose que tout le monde ait perdu en même temps, donc tu as bien raison.

@nimls_ Mouais, très empirique comme démonstration (i.e. pas rigoureux du tout mais quand on parle de graphes j'avoue que c'est galère de pas dire "ça se voit" \^\^)... Faut quand même que je corrige un peu : C'est pas "toutes les 30 minutes" c'est "30 minutes après que le candidat ait déjà perdu" :P .

« @ilod Justement, pendant l'épreuve il a été précisé que l'hécatombe suppose que tout le monde ait perdu en même temps, donc tu as bien raison. »
Donc il n'y a jamais d'hécatombe puisqu'à partir du moment où quelqu'un perd, il faut une minute pour que les autres perdent et au bout d'une minute, la source n'a plus perdu...

Ba si, la source perd pendant 30 minutes, donc s'il fait perdre les autres en 29 minutes, on arrivera bien à un instant t où tout le monde aura perdu (pendant 30 - t minutes)

"Mouais, très empirique comme démonstration" -> Oui, je sais bien, comme j'ai dit, je deblatere sur pas beaucoup parce que ca m'amusait :D

Pour la question 3, la reponse est soit deux soit impossible (il me semble \^\^' ). Je m'explique: Formons un triangle, et assourdissons un de ces sommets. Alors si ce sommet en question perd, il y a bien hecatombe (il y a marque quelque soit la source ). Bon le cas impossible, c'est si il n'y a qu'un gars, m'enfin je chippotte -_-" .

Heu, je ne comprends pas ta logique. Ils n'ont jamais dit qu'ils te laissaient placer les candidats comme tu veux, y a aucune raison qu'ils soient tous à portée les uns des autres.

'fin, cf mon message précédent, explique-moi comment tu fais une hécatombe en assourdissant le candidat en bout de chaîne sur une chaîne de plus de 30 candidats.

Et puis, dans un premier temps, il me semble qu'il n'y ait pas de sourds

Euh, la question 3, c'est justement celle où on doit ajouter des sourds...

Ah désolé alors …

"Heu, je ne comprends pas ta logique. Ils n'ont jamais dit qu'ils te laissaient placer les candidats comme tu veux"-> Je sais, c'etait pour prendre un exemple \^\^

" y a aucune raison qu'ils soient tous à portée les uns des autres." -> Si, l'hecatombe est possible (fin disons a porte indirect, si tu parlait de porte direct alors tu as raison :p )

"'fin, cf mon message précédent, explique-moi comment tu fais une hécatombe en assourdissant le candidat en bout de chaîne sur une chaîne de plus de 30 candidats." ->
1) Si c'est une chaine de plus de 30 candidats il n'y a pas hecatombe (or, il y a marque l'hecatombe est possible \^\^).
2)Il y a marque "quelque soit la source", donc ca veut dire que le sourd en question peut perdre aussi :D

Desole si je ne reponds pas a ta question, il se peut que j'ai mal compris :p

Franchement, le return 2 j'y ai pensé en même pas 10 minutes mais j'aurais été là le jour de l'épreuve, j'y aurais surement pensé mais j'aurais jamais osé marqué ça et j'aurais réfléchis pendant 2 heures sur des solutions sans queue ni tête en me disant que c'était trop simple \^\^ Quelle piège vicieux quand même.

Mais il fallait bien comprendre la question parce que quelque chose n'était pas clair : est-ce l'hécatombe était possible à partir de n'importe quelle source ? Ou alors est-ce que l'hécatombe était possible à partir d'un nombre limité de source... Apparemment c'était la première observation la bonne parce que, pour la deuxième et dans certains cas, un sourd aurait été suffisant.

N'empêche que si on connait pas les graphes on est presque déjà cuit pour l'épreuve écrite... et les épreuves machines > 4. HMMM.

/me est en mode étude de graphe depuis samedi...

Et dire que je suis en 2ème info et qu'on a presque rien vu sur les graphes pfff -.-'

Et je me demandais, par exemple pour le BFS qui nécessite une file, lors de l'épreuve écrite vous voulez le code des fonctions de la file qu'on utilisera ? et la structure de la file en général ? Ou ca n'a pas d'importance ?