Editing 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 &les; n &les; 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 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)

</syntaxhighlight>