Rezolvare PBinfo #4589

Liisa se joacă cu cifrele. Ea scrie pe o foaie de hârtie mai multe numere. Le privește îndelung și apoi îi vine ideea de a adăuga după fiecare cifră pară, a fiecărui număr jumătatea acesteia. Numește aceste numere, numere rezultat. Fiecărui număr rezultat, îi atașează un număr numit număr imagine, pe care îl construiește după următorul algoritm: asociază, mai intâi numărului rezultat un vector ce conține numărul de apariții al fiecărei cifre în numărul rezultat, de la cifra 0 până la cifra 9. Apoi construiește, folosind vectorul de apariții, un nou număr în care cifra unităților este restul împărțirii la 10 al numărului de apariții a celei mai mari cifre din numărul rezultat, cifra zecilor va fi restul împărțirii la 10 al numărului de apariții a următoarei celei mai mari cifre din numărul rezultat și tot așa până la epuizarea cifrelor numărului rezultat. Acest număr, este numit de Liisa, număr imagine al numărului rezultat. Când termină treaba, se hotărăște să facă din acest joc o mică problemă de informatică, pe care să o dea surorii ei să o rezolve, că tot se pregătește pentru apropiata olimpiadă de informatică.

Cerința

Cunoscând numărul N de numere și numerele scrise la început de Liisa pe foaia de hârtie, scrieţi un program care să rezolve următoarele două cerinţe:
1. Determină numerele rezultat obținute de Liisa, pentru cele N numere.
2. Determină cel mai mare dintre numerele imagine obținute și numărul său de apariții în șirul celor N numere imagine.

Date de intrare

Fișierul de intrare cifre.in conține pe prima linie două numere naturale, separate printr-un spațiu, C și N, care reprezintă cerinţa care trebuie să fie rezolvată (1 sau 2), respectiv numărul de numere scrise de Liisa pe foaia de hârtie. A doua linie din fișier conține N numere naturale și nenule, separate între ele prin spațiu, ce reprezintă numerele scrise de către Liisa pe foaia de hârtie.

Date de ieșire

Pentru cerința 1, fişierul de ieşire cifre.out va avea o singură linie ce va conține N numere naturale, separate prin spațiu, ce reprezintă numerele rezultat obținute. Dacă cerința este 2, fișierul de ieșire cifre.out va conține două numere naturale, separate prin spațiu ce reprezintă cel mai mare dintre numerele imagine obținute și numărul său de apariții în șirul celor N numere imagine .

Restricții și precizări

• 1 ≤ C ≤ 2
• 1 ≤ N ≤ 1000
• Numerele din fișierul de intrare sunt nenule și au maximum 9 cifre
• Numerele scrise în fișierul de ieșire vor avea cel mult 18 cifre

Exemplul 1:

cifre.in

1 1
7458

cifre.out

742584

Explicație

După fiecare cifră pară a numărului din șir, se inserează o cifră egală cu jumătatea acesteia, rezultând numărul rezultat.

Exemplul 2:

cifre.in

2 5
18442 4128 4289 7805609 5087069

cifre.out

41111111 2

Explicație

Se observă că din șirul de n numere se determină cel mai mare număr imagine care este 41111111 și există două numere rezultat ce obțin acest număr imagine, astfel: pentru numărul 7805609 se obține numărul rezultat 78400563009. Numărul imagine atașat lui este 41111111. Pentru numărul 5087069 se obține numărul rezultat 50084700639. Numărul imagine atașat lui este 41111111.