Corjuc Eunice: Pagină nouă: 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 n...

2024-01-04T20:28:11Z

Pagină nouă: 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 n...

New page

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>

2179 - Max 3 - Revision history