1156 - InaltimiQ
De la Universitas MediaWiki
Cerinta
Se dau înălțimile a n copii, numerotați de la 1 la n, exprimate prin numere naturale. Afișați numerele de ordine ale copiilor în ordinea crescătoare a înălțimii lor.
Pentru sortare se va folosit metoda QuickSort sau MergeSort.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând, în ordine, înălțimile copiilor.
Date de iesire
Programul va afișa pe ecran n numere naturale distincte cuprinse între 1 și n, separate prin exact un spațiu, reprezentând numerele de ordine ale copiilor în ordinea crescătoare a înălțimii.
Restrictii si precizari
- 1 ⩽ n ⩽ 1000
- înălțimile copiilor vor fi numere naturale distincte din intervalul [1 , 10000]
Exemplul 1
- Intrare
- 7
- 8 20 16 14 10 4 12
- Iesire
- Datele introduse corespund restrictiilor impuse
- 6 1 5 7 4 3 2
Exemplul 2
- Intrare
- 4
- -6 0 -10 25
- Iesire
- Datele introduse nu corespund restrictiilor impuse
Rezolvare
def verifica_date_intrare(n, inaltimi):
if not (1 <= n <= 1000):
return False
if len(inaltimi) != n or any(h < 1 or h > 10000 for h in inaltimi):
return False
return True
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i][1] < right[j][1]:
result.append(left[i])
i += 1
elif left[i][1] == right[j][1]:
if left[i][0] < right[j][0]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Citire date de intrare
try:
n = int(input())
inaltimi = list(map(int, input().split()))
# Verificare date de intrare
if not verifica_date_intrare(n, inaltimi):
raise ValueError("Datele introduse nu corespund restricțiilor impuse.")
# Adaugare numere de ordine și înălțimi într-o listă de tupluri
copii = list(enumerate(inaltimi, start=1))
# Sortare folosind MergeSort
copii_sortati = merge_sort(copii)
# Afișare rezultat
for copil in copii_sortati:
print(copil[0], end=" ")
except ValueError as ve:
print(ve)