== include(page="template/taskheader" task_id="cifre5") ==
Poveste și cerință...
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.
h2. Cerință
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ț.
h2. Date de intrare
Fișierul de intrare $cifre5.in$ ...
Fișierul de intrare $cifre5.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.
h2. Date de ieșire
În fișierul de ieșire $cifre5.out$ ...
Fișierul de ieșire $cifre5.out$ va conține 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ț.
h2. Restricții
* $... ≤ ... ≤ ...$
* 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.
h2. Exemplu
table(example).
|_. cifre5.in |_. cifre5.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
|_. cifre5.in |_. cifre5.out |_. Explicație |
| 8
3120
400
1000
50
1
0
37
60
| 14280
6410
500
10
20
10
0
7330
0
| 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.
|
...
== include(page="template/taskfooter" task_id="cifre5") ==
