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]
Une magnifique île inhabitée a été découverte au fin fond de l'océan Pacifique. De nombreux étrangers ont prévu d'émigrer vers ce petit paradis, et vous vous êtes retrouvé chargé de planifier la construction de la ville principale.

Il se trouve que la plupart des migrants sont Français et Australiens. Malheureusement, aucun des Australiens n'a jamais appris le Français et aucun des Français ne peut comprendre l'épais accent Australien.

Vous avez ainsi décidé de diviser la ville en deux secteurs. Une large rivière coule au centre de l'île, et vous prévoyez donc de placer un secteur Français d'un côté de la rivière et un secteur Australien de l'autre côté. Au milieu de la rivière, plusieurs restaurants flottants vont ouvrir et permettre aux différentes nationalités de se rencontrer et communiquer dans le langage universel du café.

Vous devez porter une attention très particulière à la manière dont vous construisez cette ville. Les résidents souhaitent que les secteurs soient aussi égaux que possible, de telle sorte qu'une nationalité n'en domine pas une autre. Ils comptabilisent précisément la surface qui a été développée de chaque côté de la rivière et vous font payer une taxe en fonction de l'importance de la différence.

Plus précisément, chaque fois que vous construisez un nouveau bâtiment, les résidents mesurent la surface totale de tous les bâtiments du côté français et la surface totale de tous les bâtiments du côté australien. Ils calculent ensuite la différence entre ces deux surfaces, et vous font payer la somme correspondante en drachmes (la seule forme de monnaie sur laquelle les deux communautés peuvent s'entendre).

Les résidents sont également assez exigeants au sujet des immeubles qu'ils veulent construire. On vous a fourni une liste exacte des immeubles qui doivent êtres créés. Vous êtes autorisé à les construire dans l'ordre de votre choix, d'un côté ou de l'autre de la rivière. Votre objectif est de décider quand et où construire ces bâtiments, pour avoir à payer la plus petite taxe possible.

Exemple

Supposez que l'on vous ait demandé trois immeubles de surfaces 2, 3 et 4. Les tableaux ci-dessous illustrent deux manières différentes possibles de construire ces immeubles.

Nouvel Immeuble Surface (Aus.) Surface (Fr.) Taxe
Surface 2, Côté Français 0 2 2
Surface 3, Côté Français 0 5 5
Surface 4, Côté Australien 4 5 1
Taxe totale 8

Nouvel Immeuble Surface (Aus.) Surface (Fr.) Taxe
Surface 3, Côté Australien 3 0 3
Surface 4, Côté Français 3 4 1
Surface 2, Côté Australien 5 4 1
taxe totale 5

La deuxième méthode est meilleure que la première, car elle donne une taxe totale inférieure : 5 drachmes.

Limites de temps et de mémoire (Python)

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

Contraintes

  • 1 <= N <= 100, où N est le nombre d'immeubles requis;
  • 1 <= A <= 100,000, où A est la surface d'un immeuble (mesurée en mètres carrés).

De plus, dans 30% des jeux de tests, aucun immeuble n'aura de surface supérieure à 100.

Entrée

Votre programme doit lire sur l'entrée standard. La première ligne contient un simple entier N, indiquant le nombre total d'immeubles requis.

Les N lignes suivantes décrivent chacune un immeuble. Chacune de ces lignes contient un simple entier, représentant la surface de l'immeuble (en mètres carrés). Notez que plusieurs immeubles peuvent avoir la même surface.

Sortie

Votre programme doit écrire sur la sortie standard la meilleure solution qu'il peut trouver. Votre sortie doit commencer par N lignes décrivant les N immeubles dans l'ordre dans lequel vous les construisez. Chacune de ces lignes doit avoir la forme A S, où A est la surface de l'immeuble et S dénote de quel côté de la rivière il est construit. La surface A doit être un entier (mesuré en mètres carrés), et S doit être une lettre minuscule "a" ou "f", indiquant respectivement le côté Australien ou Français.

Une fois que les immeubles ont été décrits, votre programme doit écrire une ligne supplémentaire sur la sortie. Cette ligne doit contenir un simple entier, représentant la taxe totale payée (en drachmes).

Exemple

entrée :

3
2
3
4

sortie :

3 a
4 f
2 a
5

Commentaires

Score

Il n'y a pas de "meilleure solution" particulière que vous devez atteindre. Votre score sera déterminé en fonction des autres candidats, contre lesquels vous concourrez (et également de la solution des juges).

Pour chaque jeu d'entrée, le candidat qui obtient la plus petite taxe totale sera déterminé. Supposons que ce candidat obtienne une taxe totale de T. De plus, soit M la surface moyenne d'un immeuble du jeu d'entrée (tel que M soit la somme de toutes les surfaces d'immeubles divisée par N). Votre score pour ce jeu d'entrée sera alors :

  • 100% si votre programme trouve une solution qui est identique à cette taxe totale minimale T.
  • 10% si votre programme trouve une solution dont la taxe totale est supérieure ou égale à T + M.
  • 0% si votre programme génère une solution incorrecte (ie, vous oubliez un immeuble, construisez le même immeuble plus d'une fois, ou ne calculez pas correctement la taxe totale).
  • sinon, votre score sera déterminé par une échelle linéaire en fonction de votre taxe totale, les scores de 100% et 10% correspondant aux solutions décrites ci-dessus.

Par exemple, considérez un jeu d'entrée pour lequel la surface moyenne d'immeuble est de M = 90. Si la meilleure solution trouvée par un candidat (ou par les juges) donne une taxe totale de 400, alors l'échelle de score pour une solution correcte sera la suivante :

Taxe totale 400 420 440 460 480 490 500 510
Score 100% 80% 60% 40% 20% 10% 10% 10%

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…