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.
De plus, dans 30% des jeux de tests, aucun immeuble n'aura de surface supérieure à 100.
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.
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).
entrée :
3 2 3 4
sortie :
3 a 4 f 2 a 5
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 :
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% |