Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]
Votre petite soeur vient de recevoir son cadeau d'anniversaire : un jeu de construction de mobiles. La boîte contient deux types d'éléments : des tiges et des décorations, comme illustré ci-dessous.

Des fils relient trois crochets à chaque tige. Celui du milieu permet d'accrocher l'ensemble de la tige sous un autre objet (soit le plafond, soit une décoration se trouvant plus haut). Une et une seule tige doit rattacher le mobile au plafond. Des deux côtés de chaque tige, des fils descendent et se terminent par un crochet. Ceci permet de suspendre une décoration sous chaque extrémité de la tige.

De nombreux types de décorations sont fournis, de différentes formes et poids. Deux anneaux sont fixés sur chaque décoration : l'un sur le dessus, l'autre en dessous. L'anneau du dessus peut être utilisé pour accrocher la décoration à un crochet se trouvant sous l'extrémité gauche ou droite d'une tige. L'anneau du dessous peut être utilisé pour y suspendre une autre tige.

Lorsque l'on construit un mobile avec ces éléments, aucun crochet ne doit être laissé libre, sauf celui du sommet, qui permet de suspendre l'ensemble du mobile au plafond. Tout autre crochet doit être attaché à une décoration. Les décorations n'ont pas autant de contraintes : certaines décorations peuvent avoir d'autres tiges qui y sont suspendues, d'autres peuvent ne rien avoir d'attaché à leur anneau inférieur. Une illustration d'un mobile complet est fournie ci-dessous. Les tiges sont numérotées de 1 à 7 et le poids de chaque décoration est indiqué à côté.

Votre petite soeur a terminé de construire un magnifique mobile, mais se plaint qu'il ne fonctionne pas ! En effet, le mobile est loin d'être bien équilibré : ce qui est suspendu d'un côté de certaines tiges est parfois bien plus lourd que ce qui est suspendu de l'autre côté.

Vous avez proposé votre aide, mais votre soeur se fâche lorsque vous lui expliquez que vous devrez déplacer certains éléments pour équilibrer le mobile. Elle ne veut pas que vous changiez quoi que ce soit à sa merveilleuse construction ! Le mobile est parfait ainsi, vous devez juste le faire marcher ! Vous finissez par la convaincre qu'il est nécessaire de changer quelque-chose pour améliorer l'équilibre, mais elle ne vous autorise à effectuer qu'une seule modification sur sa création.

Votre objectif est de rendre l'ensemble du mobile aussi équilibré que possible, en n'y apportant qu'une seule modification. Cette modification doit consister à détacher une tige de la décoration sous laquelle elle est suspendue, puis de l'attacher sous une autre décoration. Vous n'avez pas à vous inquiéter des possibilités de collisions entre les éléments du mobile lorsqu'il est mis en mouvement : vous pourrez toujours vous en occuper plus tard, en modifiant les longueurs de certains fils. Equilibrer le mobile est votre seule préoccupation.

Pour déterminer à quel point une tige donnée est équilibrée, vous devez calculer la valeur absolue de la différence entre le poids total suspendu sous chacune des deux extrémités de cette tige (une faible valeur est donc préférable). Pour évaluer l'équilibre de l'ensemble du mobile, vous devez faire la somme des différences obtenues pour toutes les tiges. Votre but est de réduire ce total à sa plus petite valeur possible en effectuant au maximum un changement. Notez que vous n'êtes pas obligé de faire un changement : vous pouvez choisir de ne rien modifier.

A noter également que lorsque vous déplacez une tige, vous ne pouvez pas l'attacher à une décoration à laquelle est déjà suspendue une tige. Les tiges, fils et crochets sont si légers qu'ils peuvent être considérés comme n'ayant pas de poids.

Limites de temps et de mémoire (Python)

  • Temps : 5 s sur une machine à 1 GHz.
  • Mémoire : 10 000 ko.

Contraintes

  • 1 <= N <= 2000, où N est le nombre de tiges;
  • 1 <= W <= 1000, où W est le poids d'une décoration.

De plus, dans 30% des jeux de tests, N <= 200.

Entrée

La première ligne de l'entrée contient un entier N, le nombre de tiges utilisées dans le mobile. Les tiges sont numérotées de 1 à N, la tige 1 étant accrochée au plafond.

Chacune des N lignes suivantes décrit une tige. Les tiges sont fournies dans l'ordre, de 1 à N (de telle sorte que la ligne 2 décrit la tige 1, et ainsi de suite). Chacune de ces lignes est de la forme W1 R1 W2 R2, où W1 et W2 sont les poids des décorations attachées directement sous les extrémités gauche et droites de la tige, et R1 et R2 sont les identifiants des tiges suspendues sous ces décorations (les tiges R1 et R2 sont suspendues respectivement sous les décorations de poids W1 et W2).

Si aucune tige n'est suspendue à une décoration, l'identifiant de tige correspondant sera zéro.

Sortie

La sortie doit consister en une ligne, contenant un simple entier : la plus petite somme de différences de poids que vous pouvez obtenir, en déplaçant au maximum une tige du mobile.

Exemple

entrée :

7
4 2 20 3
12 4 4 5
12 6 20 7
3 0 3 0
6 0 6 0
6 0 6 0
7 0 7 0

sortie :

42

Commentaires

L'entrée corresponda au grand mobile illustré plus haut.

Dans l'exemple d'entrée, les différences de poids pour les tiges 1,...,7 sont respectivement 40, 2, 10, 0, 0, 0 et 0, ce qui donne une somme totale de 52. En déplaçant la tige 7 pour la placer sous l'une des décorations attachées à la tige 5, les différences de poids deviennent 12, 12, 4, 0, 14, 0 et 0, ce qui donne un total de 42. Aucune somme inférieure ne peut être obtenue sans déplacer plus d'une tige, donc 42 est la réponse finale.

Score :

Le score pour chaque jeu de test sera 100% si la bonne réponse est fournie sur la sortie, et 0% sinon.

Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.

Correction en cours de chargement…