Editing 2179 - Max 3

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

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

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

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

1) <code>21, 321, 210</code>;

2) <code>21, 210, 321</code>;

3) <code>321, 21, 210</code>;

4) <code>321, 210, 21</code>;

5) <code>210, 21, 321</code>;

6) <code>210, 321, 21</code>;

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

1) <code>21321210</code>;

2) <code>21210321</code>;

3) <code>32121210</code>;

4) <code>32121021</code>;

5) <code>21021321</code>;

6) <code>21032121</code>.

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

= Cerința =
Scrieţi un program care să citească numărul natural nenul <code>n</code> şi cele <code>n</code> numere naturale nenule din şir şi care să determine:

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

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

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

= Date de ieșire =
Fişierul de ieşire <code>output.txt</code> va conţine:

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

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

= Restricții și precizări =
• Numărul <code>n</code> este număr natural <code>2 ≤ n ≤ 3500</code>

== Exemplul 1 ==
input.txt:

9

34 23 9 43 21 67 121 79 213

output.txt:

321

9977643433232121211

Explicație:

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

== Exemplul 2 ==
input.txt:

9999999

34 23 9 43 21 67 121 79 213

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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()

</syntaxhighlight>