Rivière

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.

• 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.

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.

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).

3
2
3
4

3 a
4 f
2 a
5

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%