Going Back to the Definitions

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Authors:
Problem type

One day, Gary woke up to realize that the foundations of mathematics had been completely restructured overnight.

It turns out that adding two numbers now means writing them side by side; that is, adding the R digit number A and the S digit number B is now defined as:

A_1A_2...A_R + B_1B_2...B_S = A_1A_2...A_RB_1B_2...B_S

For example, 123 + 45 = 12345, and 45 + 123 = 45123.

Mr. Ing draws N positive integers on the board, and he asks the class to determine the maximum possible sum of all N integers, provided they can be ordered in any way possible. Gary gets a little nervous when everyone else raises their hands almost instantly, and he needs your help to solve the question.

Input Specifications

On the first line will be N (1 \le N \le 10,000). On the next N lines, a single integer N_i (1 \le N_i \le 10^9) denoting one of the numbers Ing has written upon the board.

Output Specifications

The maximum possible sum that can be obtained by adding the N numbers together in any order. Keep in mind that the output will be possibly extremely long and thus may not fit in a C++ integer.

Sample Input 1

4
1
2
3
4

Sample Output 1

4321

Sample Input 2

4
2
32
555
16

Sample Output 2

55532216

Comments

There are no comments at the moment.