1157 - KSort2

Cerinţa

Se dă un vector cu n elemente, numere naturale și un număr k. Ordonați crescător primele k elemente ale vectorului și descrescător ultimele n-k elemente.Pentru sortare se va folosit metoda QuickSort sau MergeSort.

Date de intrare

Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.

Date de ieşire

Programul va afișa pe ecran elementele vectorului, separate prin exact un spațiu, după efectuarea operațiilor cerute.

Restricții și precizări

• 1 ⩽ k < n ⩽ 200 000
• cele n numere citite vor fi mai mici decât 1 000 000 000

Exemplul 1

Intrare

7 3
13 1 10 15 3 7 11

Ieșire

Datele introduse corespund restricțiilor impuse.
1 10 13 15 11 7 3

Exemplul 2

Intrare

fhgjfhgfgj

Ieșire

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. Definim funcția de verificare a valorilor n, k și a elementelor vectorului

def verificare(n_val, k_val, vector_verificare):

   # Verificăm dacă n și k respectă restricțiile problemei
   if 1 <= k_val < n_val <= 200000:
       # Verificăm dacă toate elementele vectorului sunt mai mici decât 1 000 000 000
       if all(x < 1000000000 for x in vector_verificare):
           # Dacă toate condițiile sunt îndeplinite, returnăm True
           return True
   return False

1. Definim funcția pentru sortarea vectorului

def sortare_vector(k_val, vector_sortare):

   # Sortăm primele k elemente în ordine crescătoare
   vector_sortare[:k_val] = sorted(vector_sortare[:k_val])
   # Sortăm ultimele elemente în ordine descrescătoare
   vector_sortare[k_val:] = sorted(vector_sortare[k_val:], reverse=True)
   # Returnăm vectorul sortat
   return vector_sortare

if __name__ == '__main__':

   try:
       # Citim numărul de elemente din vector
       n = int(input("Introduceti numarul de elemente din vector: "))
       # Citim numărul k
       k = int(input("Introduceti numarul k: "))
       # Citim elementele vectorului
       vector = list(map(int, input("Introduceti elementele vectorului: ").split()))

       # Verificăm dacă datele introduse sunt valide
       if verificare(n, k, vector):
           # Dacă datele sunt valide, afișăm un mesaj de confirmare
           print("Datele introduse corespund restricțiilor impuse.")
           # Sortăm vectorul și afișăm rezultatul
           print(' '.join(map(str, sortare_vector(k, vector))))
       else:
           print("Datele introduse nu corespund restricțiilor impuse.")
   # Tratăm cazul în care datele introduse nu sunt numere
   except ValueError:
       print("Datele introduse nu corespund restricțiilor impuse.")

</syntaxhighlight>