1156 - InaltimiQ: Diferență între versiuni
De la Universitas MediaWiki
Linia 36: | Linia 36: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python3" line="1"> | <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): | def merge_sort(arr): | ||
if len(arr) <= 1: | if len(arr) <= 1: | ||
Linia 74: | Linia 83: | ||
# Citire date de intrare | # Citire date de intrare | ||
n = int(input()) | try: | ||
inaltimi = list(map(int, input().split())) | 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 | # Adaugare numere de ordine și înălțimi într-o listă de tupluri | ||
copii = list(enumerate(inaltimi, start=1)) | copii = list(enumerate(inaltimi, start=1)) | ||
# Sortare folosind MergeSort | # Sortare folosind MergeSort | ||
copii_sortati = merge_sort(copii) | copii_sortati = merge_sort(copii) | ||
# Afișare rezultat | # Afișare rezultat | ||
for copil in copii_sortati: | for copil in copii_sortati: | ||
print(copil[0], end=" ") | |||
except ValueError as ve: | |||
print(ve) | |||
</syntaxhighlight> | </syntaxhighlight> |
Versiunea curentă din 29 decembrie 2023 12:03
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)