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 până la cifra . Apoi construiește, folosind vectorul de apariții, un nou număr, în care cifra unităților este restul împărțirii la al numărului de apariții a celei mai mari cifre din numărul rezultat, cifra zecilor va fi restul împărțirii la 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ță
Cunoscând numărul 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:
- Determină numerele rezultat obținute de Liisa, pentru cele numere.
- Determină cel mai mare dintre numerele imagine obținute și numărul său de apariții în șirul celor numere imagine.
Date de intrare
Fişierul de intrare cifre.in
conţine pe prima linie două numere naturale, separate printr-un spațiu, și , care reprezintă cerinţa care trebuie să fie rezolvată ( sau ), respectiv numărul de numere scrise de Liisa pe foaia de hârtie. A doua linie din fișier conține 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 , fişierul de ieşire cifre.out
va avea o singură linie ce va conține numere naturale, separate prin spațiu, ce reprezintă numerele rezultat obținute.
Dacă cerința este , 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 numere imagine.
Restricții și precizări
- Numerele din fișierul de intrare sunt nenule și au maxim cifre.
- Numerele scrise în fișierul de ieșire vor avea cel mult cifre.
- Pentru rezolvarea corectă a primei cerințe se obțin de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se obțin de puncte.
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 numere se determină cel mai mare număr imagine care este și există două numere rezultat ce obțin acest număr imagine, astfel: pentru numărul se obține numărul rezultat . Numărul imagine atașat lui este . Pentru numărul se obține numărul rezultat . Numărul imagine atașat lui este .