Fișierul intrare/ieșire cifre5.in, cifre5.out Sursă ONI 2014 clasa a 8-a
Autor Carmen Popescu Adăugată de avatar Isabela_coman 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii