1056 - Unific

Enunt

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 alipirea 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 unificIN.txt 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 unificOUT.txt 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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 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 numere 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.

Exemplul 1:

unificIN.txt

10
6
47
67
40
123
231
1238
331
2035
50007

unificOUT.txt

3
2
0 837

Explicație

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

Exemplul 1:

unificIN.txt

100001
6
47
67
40
123
231
1238
331
2035
50007

unificOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n, numere):

   if not (1 <= n <= 100000):
       return False

   for numar in numere:
       if not (0 <= numar <= 10**18):
           return False

   return True

def main():

   with open("unificIN.txt", "r") as fin, open("unificOUT.txt", "w") as fout:
       n = int(fin.readline().strip())
       numere = []

       for _ in range(n):
           line = fin.readline().strip()
           if line:
               numere.append(int(line))

       if not verifica_restrictii(n, numere):
           fout.write("Datele nu corespund restrictiilor impuse")
           return

       frec = [0] * 11
       st = []

       def cifre(x):
           while x:
               frec[x % 10] += 1
               x //= 10

       def verif(poz):
           aux1 = [0] * 11
           x = st[poz - 1]
           if x == 0:
               aux1[0] += 1

           while x:
               aux1[x % 10] += 1
               x //= 10

           y = st[poz]
           if y == 0 and aux1[0] != 0:
               return 1

           while y:
               if aux1[y % 10] != 0:
                   return 1
               y //= 10
           return 0

       def getnum(dr):
           f = [0] * 21
           unu = [0] * 21
           doi = [0] * 21
           cif1, cif2 = 0, 0
           x, y = st[dr - 1], st[dr]
           st_num, drr = 0, 0
           concatenate = False
           ok = False

           if x == 0:
               f[0] += 1
               unu[cif1] = 0
               cif1 += 1
           if y == 0:
               f[0] += 1
               doi[cif2] = 0
               cif2 += 1
           while x:
               cif1 += 1
               unu[cif1] = x % 10
               f[x % 10] += 1
               x //= 10
           while y:
               if f[y % 10] != 0:
                   f[y % 10] = -1
               cif2 += 1
               doi[cif2] = y % 10
               y //= 10

           for i in range(cif1, 0, -1):
               if f[unu[i]] != -1:
                   st_num = 10 * st_num + unu[i]
                   ok = True
           for i in range(cif2, 0, -1):
               if f[doi[i]] != -1:
                   drr = 10 * drr + doi[i]
                   ok = True
                   concatenate = True

           if not ok:
               return -1

           if concatenate:
               p = 10
               while drr >= p:
                   p *= 10
               return st_num * p + drr

           return st_num

       for numar in numere:
           cifre(numar) 
           st.append(numar)  

           while len(st) >= 2 and verif(len(st) - 1):
               x = getnum(len(st) - 1)
               if x != -1:
                   st[-2] = x
                   st.pop()
               else:
                   st.pop()
                   st.pop()

       maxi, afis = max((val, idx) for idx, val in enumerate(frec))

       fout.write(f'{afis}\n')
       fout.write(f'{len(st)}\n')
       for numar in st:
           fout.write(f'{numar} ')

if __name__ == "__main__":

   main()

</syntaxhighlight>