Fișierul intrare/ieșire	unific.in, unific.out	Sursă	OJI 2013 clasa a 7-a
Autor	Eugen Nodea	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1.6 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Unific (clasa a 7-a)

Notă: această problemă a fost modificată pentru a elimina inconsistențe în enunț.

Se consideră un șir A=(A₁, A₂, ..., A_N), format din N numere naturale nenule. Două numere se consideră vecine dacă se află pe poziții alăturate (A_i are ca vecini pe A_i-1 și A_i+1, pentru orice 1 < i < N, A₁ are ca vecin doar pe A₂, iar A_N are ca vecin doar pe A_N-1).

Dacă două elemente vecine A_i, A_i+1 (1 ≤ i < N) au cel puțin o cifră comună, ele se pot unifica. Procedeul de unificare constă în eliminarea din numerele A_i și A_i+1 a tuturor cifrelor comune și adăugarea prin alipire a numărului obținut din A_i+1 la numărul obținut din A_i, formându-se astfel un nou număr. Numărul A_i va fi înlocuit cu noul număr, iar numărul A_i+1 va fi eliminat din șir. (De exemplu, numerele A_i=23814 și A_i+1=40273 au cifrele 2, 3, 4 comune, după unificare obținem A_i=817, iar A_i+1 este eliminat; observați că dacă după eliminarea cifrelor comune, numerele încep cu zerouri nesemnificative, acestea vor fi eliminate, apoi se realizează alipirea). Dacă în urma eliminării cifrelor comune, unul dintre numere nu mai are cifre, atunci numărul rezultat va avea cifrele rămase în celălalt. Dacă în urma eliminării cifrelor comune atât A_i cât și A_i+1 nu mai au cifre, atunci ambele numere vor fi eliminate din șir, fără a fi înlocuite cu o altă valoare.

Ordinea în care se fac unificările în șir este importantă: la fiecare pas se alege prima pereche de elemente vecine A_i A_i+1 care poate fi unificată, considerând șirul parcurs de la stânga la dreapta. (De exemplu, considerând A_i=123, A_i+1=234, A_i+2=235, se unifică A_i cu A_i+1 => A_i=14, iar unificarea cu următorul număr nu mai este posibilă).

Cerință

Cunoscându-se șirul celor N numere naturale, să se determine:
a) cifra care apare cel mai frecvent în scrierea tuturor celor N numere; dacă există mai multe cifre cu aceeași frecvență de apariție maximă, se va reține cea mai mică cifră.
b) șirul obținut prin efectuarea unui număr maxim de unificări, după regulile descrise în enunț.

Date de intrare

Fișierul de intrare unific.in conține pe prima linie o valoare naturală N, iar pe următoarele N linii, în ordine, cele N numere naturale din șirul A, câte un număr pe o linie.

Date de ieșire

Fișierul de ieșire unific.out va conține pe prima linie un număr natural C reprezentând cifra care apare cel mai frecvent în scrierea celor N numere naturale. Pe cea de a doua linie un număr natural Nr reprezentând numărul de numere naturale rămase în șir după efectuarea unui număr maxim de unificări. Pe cea de a treia linie se vor scrie cele Nr numere naturale rămase, în ordinea din șir, separate prin câte un spațiu.

Dacă în urma procedeului de unificare, toate numerele vor fi eliminate, fișierul de ieșire va conține o singură linie, pe care se va scrie cifra care apare cel mai frecvent în scrierea celor N numere naturale.

Restricții

• 1 ≤ N ≤ 100 000
• Numerele din șirul inițial, precum și numerele obținute în urma unificărilor, nu vor depăși 10¹⁸.
• Pentru datele de test șirul obținut în urma unificărilor este nevid.
• Pentru 30% dintre teste N ≤ 1000
• Pentru 70% dintre teste numerele naturale din șir au cifrele nenule.
• Pentru determinarea corectă a primei cerințe se acordă 10% din punctajul pe test. Punctajul integral se acordă pe ambele cerințe rezolvate corect.

Exemplu