2179 - Max 3

Fie n un număr natural nenul şi un şir de n numere naturale nenule, fiecare număr din şir având cel mult 3 cifre. Şirul dat se „maximizează” prin aplicarea următoarelor transformări:

T1: Fiecare număr y din şir este înlocuit cu cel mai mare număr care se poate obţine prin aranjarea tuturor cifrelor lui y. De exemplu, pentru y=102, prin aranjarea cifrelor, se obţin numerele: 12, 21, 102, 120, 201, 210, cel mai mare număr fiind 210. Astfel, y se va înlocui în şir cu numărul 210.

T2: Se schimbă ordinea numerelor din şirul obţinut după aplicarea transformării T1 astfel încât numărul x obţinut prin alipirea tuturor numerelor din şir, în ordinea în care apar după schimbare, să fie cel mai mare posibil.

De exemplu,pentru n=3 şi şirul: 12, 132, 102,după aplicarea transformării T1 noul şir este format din numerele: 21, 321, 210. Din acest şir, se pot obţine, prin schimbarea ordinii numerelor, următoarele 6 şiruri:

1) 21, 321, 210;

2) 21, 210, 321;

3) 321, 21, 210;

4) 321, 210, 21;

5) 210, 21, 321;

6) 210, 321, 21;

Numerele care rezultă prin alipirea numerelor din fiecare şir obţinut sunt:

1) 21321210;

2) 21210321;

3) 32121210;

4) 32121021;

5) 21021321;

6) 21032121.

După aplicarea transformării T2, şirul „maximizat” este: 321, 21, 210 deoarece cel mai mare număr dintre cele 6 obţinute este x=32121210.

Cerința

Scrieţi un program care să citească numărul natural nenul n şi cele n numere naturale nenule din şir şi care să determine:

a) cel mai mare număr m din şirul de numere obţinut în urma aplicării transformării T1;

b) numărul x obţinut prin alipirea numerele din şirul „maximizat” rezultat în urma aplicării transformării T2.

Date de intrare

Fişierul de intrare input.txt conţine două linii. Pe prima linie este scris numărul natural nenul n, iar pe a doua linie sunt scrise cele n numere naturale nenule din şir, separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire output.txt va conţine:

− pe prima linie numărul natural m, reprezentând cel mai mare număr din şirul de numere obţinut în urma aplicării transformării T1;

− pe a doua linie numărul natural x, reprezentând numărul obţinut prin alipirea numerelor din şirul „maximizat”, rezultat în urma aplicării transformării T2.

Restricții și precizări

• Numărul n este număr natural 2 ≤ n ≤ 3500

Exemplul 1

input.txt:

9

34 23 9 43 21 67 121 79 213

output.txt:

321

9977643433232121211

Explicație:

După aplicarea transformării T1, şirul devine: 43, 32, 9, 43, 21, 76, 211, 97, 321. Cel mai mare număr din acest şir este m=321. După aplicarea transformării T2, şirul maximizat este: 9, 97, 76, 43, 43, 32, 321, 21, 211 iar numărul x=9977643433232121211

Exemplul 2

input.txt:

9999999

34 23 9 43 21 67 121 79 213

Output:

Constrangeri neindeplinite

Rezolvare

def ver(n):
    if not(2<=n<=3500):
        print("Constrangeri neindeplinite")
        exit()

def main():
    with open("input.txt", "r") as f:
        n = int(f.readline().strip())
        ver(n)
        v = [0] * 3502
        maxi = -1
        freq = [0] * 1000

        for line in f:
            v = list(map(int, line.split()))

        for i in range(0, n):
            aux = v[i]
            nrc = 0
            nr = 0

            while aux:
                nrc += 1
                aux //= 10

            cif = [0] * (nrc + 1)
            cnt = 0
            aux = v[i]

            while aux:
                cnt += 1
                cif[cnt] = aux % 10
                aux //= 10

            cif[1:cnt+1] = sorted(cif[1:cnt+1])

            while cnt:
                nr *= 10
                nr += cif[cnt]
                cnt -= 1

            v[i] = nr

            if v[i] > maxi:
                maxi = v[i]

        for i in range(0, n):
            freq[v[i]] += 1

        with open("output.txt", "w") as g:
            g.write(str(maxi) + "\n")

            for i in range(9, -1, -1):
                while freq[i]:
                    g.write(str(i))
                    freq[i] -= 1

                for j in range(i * 10 + 9, i * 10, -1):
                    while freq[j]:
                        g.write(str(j))
                        freq[j] -= 1

                    for k in range(j * 10 + 9, j * 10, -1):
                        while freq[k]:
                            g.write(str(k))
                            freq[k] -= 1


if __name__ == "__main__":
    main()