Je viens de faire le premier et le deuxième sans trop de problèmes, mais pour le troisième je me souviens avoir déjà essayé de le faire et ne pas avoir réussi, et je n'ai toujours pas d'idée maintenant. Un petit indice ne ferait pas de mal je pense.

Ouais, le troisième exercice est largement plus difficile. Pour commencer, je suppose que t'as trouvé une condition (simple) pour savoir si deux fibres se croisent ou pas. La deuxième chose à voir c'est que tu peux rendre la condition encore plus simple en ordonnant les fibres par leur position sur une des berges.

Voici le premier exercice: pyramide

Le mien : http://paste.awesom.eu/tcpc/LHE&hl=python3

Tiens, j'avais une question à propos de l'autre exercice intitulé Pyramides. Je trouve l'énoncé peut clair, en fait. Faut-il seulement ranger les degrés d'adhérence par ordre croissant puis additionner les n premiers termes (n correspondant au nombre d'étages) ou est-ce plus élaboré (au départ, j'avais pensé à un arbre binaire mais en fait, ça va pas) ? (Pour le coup, je trouve l'énoncé vraiment mal foutu et les exemples peu pertinents (l'arbre binaire fonctionne pour 2 ou 3 étages mais pas pour 4 ou plus, par exemple)... Un peu d'aide à la compréhension du sujet ne serait pas de refus.

On te donne le degré d'adhérence de chaque marche de la pyramide. Par exemple, pour le deuxième exemple, la pyramide est :

    811
  740 702
946 380 362

Il faut trouver un chemin entre le haut et le bas de la pyramide pour lequel la somme des degrés d'adhérence est maximale (dans ce cas : 811, 740, 946) et renvoyer cette somme (2497).

Ah, comme le texte parlait d'une case gauche et droite (et que l'exercice précédent faisait mention de deux briques en plus à chaque étage) j'avais modélisé cela comme ça (pour 4 étages, par exemple) :

   ?
  ? ?
 ?? ??
???? ????

Etc. Et donc forcément, ça clochait au niveau du nombre de degrés d'adhérence. :>

Merci gnomnain.

Voilà mon essai pour le troisième : http://paste.awesom.eu/mob/7RO&hl=cpp
Apparemment c'est pas correct. Ça fonctionne sur les exemples de l'énoncé, mais ça ne passe pas les tests sur le site de prologin.
La structure utilisée ne me plaît pas trop non plus. Au début j'utilisais une map, mais apparemment pour la trier il faut quelques artifices supplémentaires, et je voulais faire un truc rapidement.

gnomnain : Pour le premier exemple sur prologin, les fibres sont déjà triées par l'abscisse du côté gauche de la rive, mais ça n'aide pas beaucoup.

Si j'ai bien compris, tu pars d'une situation où tous les câbles sont là, et tu enlève celui qui a le plus d'intersections jusqu'à ce qu'il n'y ait plus d'intersections ? Je pense que c'est trop glouton pour marcher mais j'ai pas de contre-exemple évident.

Oui c'est bien ça.

EDIT : Sur le site de prologin ils n'indiquent pas le test utilisé, juste que la sortie attendue est 5 et que le résultat est 1...
Est-ce qu'il faut obligatoirement compléter le code fournit ? parce que j'avais déjà codé le mien avant et je l'ai soumis tel-quel.

Non, si ton code lit correctement l'entrée, il devrait marcher aussi.

Salut, bonne idée de sujet.

• Pyramide : çay moche mais bon…
• Pyramides : malheureusement ça ne passe que 5 tests sur 7, le calcul est jugé trop lent.

Je vais regarder un peu le 3ème.

Le deuxième est un algorithme dynamique. C'est ultra-classique et si tu ne connais pas ces algos, il faut que tu te formes. France-IOI a plein d'exercices sur ça, et cet énoncé ("triangle") est le plus simple d'entre eux, ou presque.

Par ailleurs j'insiste sur le fait que == n'est pas le test d'égalité structurelle en OCaml, il vaut mieux utiliser = (== fait un test d'égalité physique qui a une sémantique différente sur les valeurs construites, même si ça ne change rien sur les entiers).

Merci pour tes remarques.

Pour = et == au temps pour moi, je le sais mais je ne pratique pas assez OCaml alors j'ai tendance à écrire == par habitude.

Pour le deuxième algo, j'ai d'abord remarqué que je faisais les mêmes calculs plusieurs fois du fait que la pyramide n'est pas vraiment un arbre (les branches se recoupent). Une version corrigée est ici qui passe bien les 7 tests sur 7 et au passage utilise un array d'arrays ce qui est quand même nettement plus pratique syntaxiquement.

Par contre c'est vrai qu'un traitement de bas en haut comme le fait acieroid est plus intelligent vu qu'il évite ces Todo | Done. J'ai donc écrit ça après, qui passe aussi les 7 tests sur 7 (et ressemble fortement au code d'acieroid).

Pour la programmation dynamique, effectivement c'est quelque chose qu'il faut que je travaille, pour le moment je vois mal ce qui distingue un algo dynamique d'un autre algo. Je vais regarder tout ça plus en détail, merci bien !

pour le moment je vois mal ce qui distingue un algo dynamique d'un autre algo

Le fait de réutiliser plusieurs fois le résultat du calcul de certains sous-problèmes.

Ok, l'article français de Wikipedia sur le sujet était pas vachement clair, ça passe mieux avec la version anglaise. J'ai retrouvé un DM d'info de MPSI qui en parlait à travers une version du problème du sac à dos en comparant une solution récursive exponentielle et une solution dynamique, je vais m'y replonger.

j'ai fait le premier avec l'aide de quelques gens.

Voici mon code pour le premier. Et voici mon code pour le troisième, ce code n'est pas optimal car il est en O(n²) alors qu'il y a une solution en O(n Log n) mais je l'ai quand même écrit pour voir s'il passait les tests et il les passe.

Effectivement, la solution en O(n²) marche assez bien, c'est celle que j'ai utilisée à prologin quand je suis tombé sur cet exo.

Thomash: Si j'ai bien compris, long.(i) est le nombre de fibres que i ne croise pas et qui la précèdent ? (+1)

long.(i) est la longueur de la plus longue sous-suite croissante ayant snd coords.(i) comme dernier élément.