Adina Timiș: Pagină nouă: ==Cerința== Fie N un număr întreg impar și un vector A cu N elemente. Pentru fiecare element $A_{i}$ , acesta se poate incrementa cu 1. Fiecare element sepoate incrementa cel mult odată. Mai mult, se pot realiza cel mult K incrementări. Scopul este de a maximiza medianul lui A. Medianul unui vector este definit ca fiind elementul din mijlocul vectorului după sortarea acestuia. De exemplu, medianul vectorului [5, 8, 2, 9, 1] este 5. ==Date de intrare== Pr...

2023-05-05T19:02:46Z

Pagină nouă: ==Cerința== Fie N un număr întreg impar și un vector A cu N elemente. Pentru fiecare element <math>A_{i}</math>, acesta se poate incrementa cu 1. Fiecare element sepoate incrementa cel mult odată. Mai mult, se pot realiza cel mult K incrementări. Scopul este de a maximiza medianul lui A. Medianul unui vector este definit ca fiind elementul din mijlocul vectorului după sortarea acestuia. De exemplu, medianul vectorului [5, 8, 2, 9, 1] este 5. ==Date de intrare== Pr...

New page

==Cerința==
Fie N un număr întreg impar și un vector A cu N elemente. Pentru fiecare element <math>A_{i}</math>, acesta se poate incrementa cu 1. Fiecare element sepoate incrementa cel mult odată. Mai mult, se pot realiza cel mult K incrementări. Scopul este de a maximiza medianul lui A. Medianul unui vector este definit ca fiind elementul din mijlocul vectorului după sortarea acestuia. De exemplu, medianul vectorului [5, 8, 2, 9, 1] este 5.
==Date de intrare==
Prima linie conține un număr impar N și un întreg K. Pe a doua linie se află N numere separate prin spații naturale, reprezentând elementele vectorului.
==Date de ieșire==
Programul va afișa pe ecran numărul ce reprezintă maximul posibil al medianului după aplicarea operațiilor de incrementare.
==Restricții și precizări==
*1 ≤ k ≤ n ≤ 1000, N e impar;
*1 ≤ <math>A_{i}</math> ≤ 1000;
==Exemplul 1==
;Intrare
:9 3
:4 4 4 8 2 2 9 9 1
;Ieșire
:Datele de intrare corespund restricțiilor impuse.
:5
==Explicație==
:Se pot incrementa elementele de pe pozițiile 1, 2 și 3. Valoarea comună reprezintă medianul maxim care se poate obține.
==Exemplul 2==
;Intrare
:0 0
:0 0
;Ieșire
:Datele de intrare nu corespund restricțiilor impuse.
==Rezolvare==
<syntaxhighlight lang="python" line="1">
#3406 - As Easy As ABC
def maximize_median(vector, k):
n = len(vector)
mid = n // 2
median = vector[mid]

# pentru a crește valoarea medianei, vom parcurge elementele din stânga acesteia
for i in range(mid - 1, -1, -1):
if k <= 0:
break
# calculăm diferența dintre valoarea medianei și elementul curent i, din stânga ei
# această diferență trebuie să fie mai mică sau egală cu numărul de operații disponibile k
diff = min(vector[mid] - vector[i], k // (mid - i))
# creștem valoarea medianei cu diferența calculată
median += diff
# scădem din numărul total de operații k, numărul de operații realizate, pentru a crește valoarea medianei
k -= diff * (mid - i)

# pentru a crește valoarea medianei, vom parcurge elementele din dreapta medianei
for i in range(mid + 1, n):
if k <= 0:
break
# calculăm diferența dintre elementul curent i din dreapta medianei și valoarea acesteia
# diferența trebuie să fie mai mică sau egală cu numărul de operații disponibile k
diff = min(vector[i] - vector[mid], k // (i - mid))
# creștem valoarea medianei cu diferența calculată
median += diff
# scădem din numărul total de operații k, numărul de operații realizate pentru a crește valoarea medianei
k -= diff * (i - mid)

# returnăm valoarea maximă a medianei
return median

if __name__ == "__main__":
# citim numărul n de elemente din vector și numărul k de operații care pot fi realizate
# elementele vectorului sunt sub forma de listă de numere
n, k = map(int, input().split())
vector = list(map(int, input().split()))

# verificăm restricțiile
if n % 2 == 0 or n < 1 or n > 1000 or k < 1 or k > n or any(a < 1 or a > 1000 for a in vector):
print("Datele de intrare nu corespund restricțiilor impuse.")
else:
print("Datele de intrare corespund restricțiilor impuse.")
vector.sort()
max_median = maximize_median(vector, k)
# în caz contrar, apelăm funcția și afișăm valoarea maximă a medianei
print(max_median)

</syntaxhighlight>

3406 - As Easy As ABC - Revision history