acm

cz

acm

cz

Dept. of Computer Science and Engineering, Czech Technical University in Prague

Faculty of Mathematics and Physics, Charles University in Prague

Faculty of Electrical Engineering and Computer Science, Technical University of Ostrava

Faculty of Informatics and Information Technologies, Slovak University of Technology

Faculty of Informatics, Masaryk University

Faculty of Management Science and Informatics, University of Zilina

CTU Open Contest 2008

Government Help

help.c, help.C, help.java, help.p

Two major banks in our country are knee-deep in troubles. We will call them “Bank A" and

“Bank B" — hopefully you understand we absolutely cannot tell you their real names. It might

ruin them.

As a logical consequence of their troubles, government comes to rescue them, preparing a set

of financial “packages" that will be distributed between these two banks. However, there is

one important condition: the packages will be given to the banks one by one and we need to

minimize the di.erence between the amount given to both banks in any particular moment.

Otherwise, one of the banks would gain a big advantage over the other.

For example, imagine that we have four packages with the values of 100 000, 110 000, 120 000,

and 150 000. If we give the first package to the Bank A, then the second one to the Bank B,

the third one to the Bank B, and the fourth package to the Bank A, the di.erence between

the help provided to the banks will be +100 000 after the first package, -10 000 after the second

one, -130 000 after the third one, and +20 000 after the last package. The maximal di.erence is

therefore 130 000.

There is a better solution, with the maximal di.erence of 100 000 only: first, give 100 000 to the

Bank A, then 120 000 to the Bank B, then 110 000 to the Bank A, and then 150 000 to the Bank

B.

Input Specification

The input contains multiple sets of financial packages. Each set begins with a line containing

a single positive integer N: the number of financial packages (1 . N . 50 000). The second line

is a set of N positive integers separated by a space, all of them between 100 000 and 199 999

inclusive. These numbers specify the amount of money in individual packages. Packages can be

assigned in any order, the order of numbers on the second line is therefore not important.

The last set will be followed by a line containing single zero.

Output Specification

For each set of financial packages, output one line containing the order of assignments of packages

to the banks, such as the maximal di.erence is as low as possible. If there are more possible

solutions, you may print any of them.

Assignments must be separated by a space, each assignment consists of one number (the package

size), one dash character (“-"), and an uppercase letter (“A"or“B") specifying the bank.

Sample Input

4

100000 110000 120000 150000

3

100000 100000 100000

0

Output for Sample Input

100000-A 120000-B 110000-A 150000-B

100000-B 100000-A 100000-A