Fișierul intrare/ieșire unific.in, unific.out Sursă OJI 2013 clasa a 7-a
Autor Eugen Nodea Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1.6 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Unific (clasa a 7-a)

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

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

Dacă două elemente vecine Ai, Ai+1 (1 ≤ i < N) au cel puțin o cifră comună, ele se pot unifica. Procedeul de unificare constă în eliminarea din numerele Ai și Ai+1 a tuturor cifrelor comune și adăugarea prin alipire a numărului obținut din Ai+1 la numărul obținut din Ai, formându-se astfel un nou număr. Numărul Ai va fi înlocuit cu noul număr, iar numărul Ai+1 va fi eliminat din șir. (De exemplu, numerele Ai=23814 și Ai+1=40273 au cifrele 2, 3, 4 comune, după unificare obținem Ai=817, iar Ai+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 Ai cât și Ai+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 Ai Ai+1 care poate fi unificată, considerând șirul parcurs de la stânga la dreapta. (De exemplu, considerând Ai=123, Ai+1=234, Ai+2=235, se unifică Ai cu Ai+1 => Ai=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 1018.
  • 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

unific.in unific.out Explicații
10
6
47
67
40
123
231
1238
331
2035
50007
3
2
0 837
Cifra care apare cel mai frecvent este 3 (de 6 ori).
Se unifică: 47 cu 67 => 46. Șirul rămas: 6 46 40 123 231 1238 331 2035 50007
Se unifică: 6 cu 46 => 4. Șirul rămas: 4 40 123 231 1238 331 2035 50007
Se unifică: 4 cu 40 => 0. Șirul rămas: 0 123 231 1238 331 2035 50007
Se unifică: 123 cu 231, ambele numere rămân fără cifre, deci vor fi ambele eliminate.
Șirul rămas: 0 1238 331 2035 50007
Se unifică: 1238 cu 331 => 28. Șirul rămas: 0 28 2035 50007
Se unifică: 28 cu 2035 => 835. Șirul rămas: 0 835 50007
Se unifică: 835 cu 50007 => 837. Șirul rămas: 0 837

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

Indicii de rezolvare

Arată 5 categorii