Складаємо масив

Відповідь — масив відсортований за незростанням.

Чому так? Порахуймо суму всіх конкатенацій $$$ \sum_{i=1}^n \sum_{j=i}^n \operatorname{concat}(a_i, a_j)$$$ = $$$ \sum_{i=1}^n \sum_{j=i}^n (10 \cdot a_i + a_j)$$$ = $$$ \sum_{i=1}^n (10 \cdot a_i \cdot (n - i + 1) + \sum_{j=i}^n a_j)$$$ = $$$ \sum_{i=1}^n 10 \cdot a_i \cdot (n - i + 1) + \sum_{i=1}^n \sum_{j=i}^n a_j$$$ = $$$ \sum_{i=1}^n 10 \cdot a_i \cdot (n - i + 1) + \sum_{i=1}^n i \cdot a_i$$$ = $$$ \sum_{i=1}^n a_i \cdot (10 \cdot (n - i + 1) + i)$$$ = $$$ \sum_{i=1}^n a_i \cdot (10n - 10i + 10 + i)$$$ = $$$ \sum_{i=1}^n a_i \cdot (10n - 9i + 10)$$$ = $$$ \sum_{i=1}^n a_i \cdot (10n + 10) - \sum_{i=1}^n a_i \cdot 9i$$$

Перша частина не змінюється від перестановки масиву $$$a$$$, а щоб мінімізувати значення другої суми, треба відсортувати масив за незростанням. Доводиться просто — якщо є два елементи $$$a_i, a_j$$$, що $$$a_i < a_j$$$ та $$$i < j$$$, то їх можна поміняти місцями й відповідь не збільшиться.