1156 - InaltimiQ

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

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

1. Citire date de intrare

n = int(input()) inaltimi = list(map(int, input().split()))

1. Adaugare numere de ordine și înălțimi într-o listă de tupluri

copii = list(enumerate(inaltimi, start=1))

1. Sortare folosind MergeSort

copii_sortati = merge_sort(copii)

1. Afișare rezultat

for copil in copii_sortati:

   print(copil[0], end=" ")

</syntaxhighlight>