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

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)