2732 – Succesor

Sursa: Succesor

---

Cerinţă

Se consideră vectorul ordonat strict crescător sir = (sir[1], sir[2], ..., sir[k]) ce memorează o submulțime de k elemente a mulțimii {1, 2, ..., n}. Trebuie determinată următoarea submulțime din punct de vedere lexicografic. De exemplu, dacă n=4 și k=3, atunci submulțimile de trei elemente, în ordine lexicografică, sunt: {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}.

Date de intrare

Programul va citi de la tastatură valoarean, apoi k, apoi n numere întregi reprezentând elementele șirului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte!", apoi se va afișa noul vector, obținut în urma determinării următoarei submulțimi din punct de vedere lexicografic. În cazul în care datele nu respectă restricțiile, se va afișa mesajul "Datele introduse nu sunt corecte!".

Restricţii şi precizări

• 1 < k < n < 30.000
• valorile elementelor șirului vor fi < 1.000.000.000

Exemple

Exemplul 1

Intrare

Introduceti elementul n: 9

Introduceti numarul de elemente a sirului: 5

Introduceti 5 numere separate prin spatiu:2 4 5 8 9

Ieșire

Datele introduse sunt corecte!

[2, 4, 6, 7, 8]

Exemplul 2

Intrare

Introduceti elementul n: 10

Introduceti numarul de elemente a sirului: 2

Introduceti 2 numere separate prin spatiu:14 12 3

Ieșire

Datele introduse sunt incorecte!

Rezolvare

def is_integer(value):
    return value.isdigit()


def verificare_nr_elemente(k, n):
    if is_integer(k):
        if 1 < int(k) <= int(n):
            return k
        else:
            print("Datele introduse sunt incorecte!")
            exit()
    else:
        print("Datele introduse sunt incorecte!")
        exit()


def verif_ordonare(lst):
    for i in range(1, len(lst)):
        if lst[i] < lst[i-1]:
            print("Datele introduse sunt incorecte!")
            exit()
    return True


def verificare_vector(k, vector, n):
    if len(vector) != int(k):
        print("Datele introduse sunt incorecte!")
        exit()
    else:
        for i in vector:
            if is_integer(i):
                if 1 <= int(i) <= int(n):
                    continue
                else:
                    print("Datele introduse sunt incorecte!")
                    exit()
            else:
                print("Datele introduse sunt incorecte!")
                exit()
    verif_ordonare(vector)


def verificare_n(n):
    if is_integer(n):
        if 2 <= int(n) <= 30000:
            return n
        else:
            print("Datele introduse sunt incorecte!")
            exit()
    else:
        print("Datele introduse sunt incorecte!")
        exit()


def succesor(sir, n, k):
    i = k - 1
    while i >= 0 and sir[i] == n - k + i + 1:
        i -= 1
    if i >= 0:
        sir[i] += 1
        for j in range(i+1, k):
            sir[j] = sir[j-1] + 1
    print(sir)


if __name__ == '__main__':
    n = input("Introduceti elementul n: ")
    verificare_n(n)
    k = input("Introduceti numarul de elemente a sirului: ")
    verificare_nr_elemente(k,n)
    elem = input(f"Introduceti {k} numere separate prin spatiu:").split()
    verificare_vector(k, elem, n)
    lst_int = list(map(int, elem))
    print("Datele introduse sunt corecte!")
    succesor(lst_int, int(n), int(k))

Explicație rezolvare

Funcția is_integer(value) verifică dacă valoarea value este un număr întreg, returnând True dacă este și False în caz contrar.

Funcția verificare_nr_elemente(k, n) verifică dacă numărul k este un număr întreg și se află între 1 și n, returnând k în cazul în care este valid, iar în caz contrar, afișează un mesaj de eroare și iese din program cu exit().

Funcția verif_ordonare(lst) verifică dacă elementele listei lst sunt în ordine crescătoare, comparând fiecare element cu elementul anterior. În cazul în care nu sunt în ordine crescătoare, afișează un mesaj de eroare și iese din program cu exit(). Dacă toate elementele sunt în ordine crescătoare, returnează True.

Funcția verificare_vector(k, vector, n) verifică dacă lungimea listei vector este egală cu k și dacă toate elementele sunt întregi și se află între 1 și n. Dacă există elemente invalide sau lista nu este ordonată crescător, afișează un mesaj de eroare și iese din program cu exit(). Dacă toate elementele sunt valide și lista este ordonată crescător, funcția se încheie cu succes.

Funcția verificare_n(n) verifică dacă numărul n este un număr întreg și se află între 2 și 30000, returnând n în cazul în care este valid, iar în caz contrar, afișează un mesaj de eroare și iese din program cu exit().

Funcția succesor(sir, n, k) primește lista sir, reprezentând submulțimea de k elemente din mulțimea {1,2,...,n}, și returnează succesorul lexicografic al acestei submulțimi, adică următoarea submulțime de k elemente din mulțimea {1,2,...,n}, ordonată crescător. Pentru a găsi succesorul, se parcurge lista de la dreapta la stânga și se caută prima poziție i pentru care sir[i] nu este egal cu n - k + i + 1. Dacă se găsește o astfel de poziție, se incrementează sir[i] cu 1 și se ajustează restul elementelor astfel încât să formeze o submulțime ordonată crescător. Dacă nu există o astfel de poziție, submulțimea inițială era deja maximă și succesorul nu există.

În if __name__ == '__main__':, se citesc valorile n și k, se verifică dacă sunt valide folosind funcțiile verificare_n și verificare_nr_elemente, apoi se citește lista elem și se verifică folosind funcția verif_ordonare. Aceasta parcurge elementele vectorului și verifică dacă fiecare element este mai mare sau egal cu cel anterior. Dacă se găsește un element care nu respectă această condiție, programul afișează mesajul "Datele introduse sunt incorecte!" și se oprește cu exit().

În continuare, se verifică elementele vectorului dacă respectă intervalul impus, adică să fie între 1 și n, folosind funcția verificare_vector. Dacă un element nu se încadrează în acest interval, programul afișează mesajul "Datele introduse sunt incorecte!" și se oprește cu exit().

Se afișează mesajul "Datele introduse sunt corecte!" și se apelează funcția succesor, care primește ca parametri vectorul, n și k. Funcția calculează succesorul submulțimii memorate inițial în vectorul a și afișează rezultatul.