Rezolvare PBinfo #1207

Maia tocmai a învăţat la şcoală să facă adunări cu numere naturale având mai multe cifre. Pentru că îi place foarte mult matematica s-a apucat să scrie pe o foaie multe numere naturale, cu una sau mai multe cifre, şi a început să le adune.

După o vreme s-a cam plictisit şi s-a gândit să afle cea mai mare sumă ce s-ar putea obţine dacă s-ar schimba între ele cifrele numerelor de pe foaie. Are însă o singură dorinţă: după ce schimbă cifrele între ele să rămână acelaşi număr de numere cu o cifră, acelaşi număr de numere cu două cifre şi aşa mai departe.

Cerinţe

Scrieţi un program care să determine

a) suma maximă ce se poate obţine schimbând între ele cifrele numerelor iniţiale;
b) un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

Date de intrare

Fișierul de intrare cifre9.in conține pe prima linie un număr natural n reprezentând numărul de numere scrise de Maia pe foaie. Următoarele n linii conţin cele n numere naturale scrise iniţial pe foaie, câte un număr pe fiecare linie.

Date de ieșire

Fișierul de ieșire cifre9.out va conține pe prima linie pe prima linie un număr natural S reprezentând suma maximă obţinută. Pe următoarele n linii vor fi scrise n numere naturale, câte un număr pe o linie, reprezentând un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

Restricții și precizări

• 2 ≤ n ≤ 100 000
• Numerele din şirul iniţial sunt numere naturale ≤ 2^30-1
• Numerele din şirul afişat nu vor conţine zerouri nesemnificative.
• Dacă există mai multe şiruri pentru care se obţine suma maximă conform restricţiilor din enunţ, se va afişa oricare dintre acestea.
• Pentru afişarea corectă a sumei maxime se acordă 40% din punctaj, punctajul integral obţinându-se pentru rezolvarea corectă a ambelor cerinţe.

Exemplu:

cifre9.in

8
3120
400
1000
50
1
0
37
60

cifre9.out

14280
6410 
500
10 
20 
10 
0 
7330
0

Explicație

Se observă că atât în şirul iniţial, cât şi în cel final sunt 2 numere de 4 cifre, un număr de 3 cifre, 3 numere de două cifre şi două numere de o cifră.

De asemenea, numerele din şirul afişat conţin în total aceleaşi cifre ca numerele din şirul din fişierul de intrare.

Suma maximă care se poate obţine este 14280.