Editing 3196 - Instabook

Sursa: [https://www.pbinfo.ro/probleme/3196/instabook]
== 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 primește ca date de intrare un număr întreg n, un număr întreg k și o listă v de n numere întregi și sortează primii k elemente ai listei v în ordine crescătoare, folosind o implementare a algoritmului de sortare prin selecție.

Funcțiile '''read_input_file''' și '''write_output_file''' se ocupă de citirea datelor de intrare din fișierul cu extensia ".in" și scrierea datelor de ieșire în fișierul cu extensia ".out". Funcția min_element_index returnează indexul elementului minim dintr-un interval specificat, iar funcția '''sort_k_elements''' sortează primii k elemente ai listei v.

Funcția validate_input verifică dacă datele de intrare corespund cerințelor. Dacă valorile n și k nu sunt între 1 și 1000, respectiv 1 și n(n-1)/2, funcția afișează un mesaj corespunzător și programul se încheie. În caz contrar, funcția afișează un mesaj corespunzător și programul continuă cu sortarea listei v.