3358 - gama

Sursa: [1]

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 ⩽ n ⩽ 1000
• 1 ⩽ k ⩽ n•(n-1)/2

Exemplul 1

Intrare

gama.in

0 0

0 0 0 0

Ieșire

Datele introduse nu corespund cerintelor.

Exemplul 2

Intrare

gama.in

4 2

3 2 1 4

Ieșire

Datele introduse corespund cerintelor.

gama.out

1 3 2 4

Rezolvare

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)

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.