3406 - As Easy As ABC



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

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 ≤ $A_{i}$ ≤ 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">

1. 3406 - As Easy As ABC

def maximize_median(vector, k):

   n = len(vector)
   mid = n // 2
   median = vector[mid]

1. 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

1. calculăm diferența dintre valoarea medianei și elementul curent i, din stânga ei
2. 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

1. 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)

1. 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

1. 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>