Fișierul intrare/ieșire | cifre5.in, cifre5.out | Sursă | ONI 2014 clasa a 8-a |
---|---|---|---|
Autor | Carmen Popescu | Adăugată de | Coman Isabela Patricia • Isabela_coman |
Timp de execuție pe test | 0.7 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Cifre5 (clasa a 8-a)
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ță
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 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.
Date de ieșire
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ț.
Restricții
- 2 ≤ n ≤ 100 000
- Numerele din șirul inițial sunt numere naturale ≤ 230-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
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. |