Editing 3358 - gama

Sursa: [https://www.pbinfo.ro/probleme/3358/gama]
== Cerinţa ==
Se dă o permutare a mulțimii {1, 2, ..., n} adică un șir cu n numere distincte cuprinse între 1 și n. Se mai dă și o valoare k. Fiind permise maximum k interschimbări de elemente aflate pe poziții consecutive, se cere determinarea permutării minime din punct de vedere lexicografic.

== Date de intrare ==
Fișierul gama.in conține pe prima linie numerele naturale n și k separate printr-un spațiu. Pe linia a doua se află elementele șirului dat, separate printr-un spațiu.

== Date de ieșire == 
Fișierul '''gama.out''' conține pe primul rând n numere naturale, distincte de la 1 la n, separate prin câte un spațiu, reprezentând permutarea obținută, iar in consolă se va afișa mesajul "Datele introduse corespund cerintelor." În cazul în care datele de intrare sunt invalide programul va afișa în consolă mesajul "Datele introduse nu corespund cerintelor."

== Restricţii şi precizări ==
* 1 &les; '''n''' &les; 1000
* 1 &les; '''k''' &les; n•(n-1)/2

== Exemplul 1 ==
; Intrare
: ''gama.in''
: 0 0
: 0 0 0 0
; Ieșire
: Datele introduse nu corespund cerintelor.
<br>

== Exemplul 2 ==
; Intrare
: ''gama.in''
: 4 2
: 3 2 1 4
; Ieșire
: Datele introduse corespund cerintelor.
: ''gama.out''
: 1 3 2 4
<br>

== Rezolvare == 
<syntaxhighlight lang="python" line>
import math


def read_input_file(nume):
    with open(nume + '.in', 'r') as fin:
        n, k = map(int, fin.readline().split())
        v = list(map(int, fin.readline().split()))
        return n, k, v


def write_output_file(nume, v):
    with open(nume + '.out', 'w') as fout:
        fout.write(' '.join(str(x) for x in v))


def min_element_index(v, start, end):
    minn = math.inf
    pozMin = start
    for i in range(start, end + 1):
        if v[i] < minn:
            minn = v[i]
            pozMin = i
    return pozMin


def sort_k_elements(n, k, v):
    for i in range(0, n):
        if k == 0:
            break
        pozMin = min_element_index(v, i, min(i + k, n))
        for j in range(pozMin, i, -1):
            v[j], v[j - 1] = v[j - 1], v[j]
            k -= 1


def validate_input(n, k):
    max_k = int(n * (n - 1) / 2)
    if not (1 <= n <= 1000 and 1 <= k <= max_k):
        print("Datele introduse nu corespund cerintelor.")
        exit()

    else:
        print("Datele introduse corespund cerintelor.")


if __name__ == '__main__':
    nume = "gama"
    n, k, v = read_input_file(nume)
    try:
        validate_input(n, k)
    except ValueError as e:
        print(e)
        exit(1)
    sort_k_elements(n, k, v)
    write_output_file(nume, v)

</syntaxhighlight>

== Explicatie rezolvare ==
Acest program sortează primele k elemente ale unui vector de dimensiune n.

Funcția '''read_input_file(nume)''' citește datele de intrare din fișierul cu numele nume.in. Prima linie din fișier conține două numere întregi separate prin spațiu, n și k. A doua linie conține n numere întregi separate prin spațiu, care reprezintă elementele vectorului. Funcția returnează dimensiunea vectorului n, numărul k și vectorul v.

Funcția '''write_output_file(nume, v)''' scrie vectorul sortat în fișierul cu numele nume.out.

Funcția '''min_element_index(v, start, end)''' primește un vector v și intervalul de indexi start și end și returnează indexul elementului minim din acest interval.

Funcția '''sort_k_elements(n, k, v)''' sortează primele k elemente ale vectorului v de dimensiune n. Sortarea se face prin găsirea elementului minim dintr-un interval și interschimbarea acestuia cu primul element din interval, apoi cu următorul element și tot așa, până când primele k elemente sunt sortate.

Funcția '''validate_input(n, k)''' verifică dacă dimensiunile vectorului și numărul k sunt în limitele cerute. Dacă nu sunt, afișează un mesaj de eroare și oprește programul.

În funcția principală''' __main__''', se specifică numele fișierului de intrare, se citește intrarea, se validează datele de intrare, se sortează primele k elemente și se scrie rezultatul în fișierul de ieșire.