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:
       mid = len(arr) // 2
       left_half = arr[:mid]
       right_half = arr[mid:]

       merge_sort(left_half)
       merge_sort(right_half)

       i = j = k = 0

       while i < len(left_half) and j < len(right_half):
           if left_half[i] <= right_half[j]:
               arr[k] = left_half[i]
               i += 1
           else:
               arr[k] = right_half[j]
               j += 1
           k += 1

       while i < len(left_half):
           arr[k] = left_half[i]
           i += 1
           k += 1

       while j < len(right_half):
           arr[k] = right_half[j]
           j += 1
           k += 1

def afiseaza_ordinea_copiilor(n, inaltimi):

   copii = list(range(1, n + 1))
   merge_sort(inaltimi)

   # Creează un dicționar pentru a ține legătura dintre înălțimi și numerele de ordine
   inaltimi_dict = dict(zip(inaltimi, copii))

   # Afișează numerele de ordine ale copiilor în ordinea crescătoare a înălțimii
   for inaltime in inaltimi:
       print(inaltimi_dict[inaltime], end=" ")

1. Citirea datelor de intrare

n = int(input("Introduceți numărul de copii: ")) inaltimi = list(map(int, input("Introduceți înălțimile copiilor separate prin spațiu: ").split()))

1. Afișarea rezultatului

afiseaza_ordinea_copiilor(n, inaltimi)

</syntaxhighlight>