View source for 2732 – Succesor

Sursa: [https://www.pbinfo.ro/probleme/2732/succesor Succesor]
----
==Cerinţă==
Se consideră vectorul ordonat strict crescător sir <code>= (sir[1], sir[2], ..., sir[k])</code> ce memorează o submulțime de <code>k</code> elemente a mulțimii <code>{1, 2, ..., n}</code>. Trebuie determinată următoarea submulțime din punct de vedere lexicografic. De exemplu, dacă <code>n=4</code> și <code>k=3</code>, atunci submulțimile de trei elemente, în ordine lexicografică, sunt: <code>{1,2,3}</code>, <code>{1,2,4}</code>, <code>{1,3,4}</code>, <code>{2,3,4}</code>.
==Date de intrare==
Programul va citi de la tastatură valoarea<code>n</code>,  apoi k, apoi <code>n</code> 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==
<syntaxhighlight lang="python" line="1">
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))






</syntaxhighlight>
==Explicație rezolvare==
Funcția <code>is_integer(value)</code> verifică dacă valoarea <code>value</code> este un număr întreg, returnând <code>True</code> dacă este și <code>False</code> în caz contrar.

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

Funcția <code>verif_ordonare(lst)</code> verifică dacă elementele listei <code>lst</code> 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 <code>exit()</code>. Dacă toate elementele sunt în ordine crescătoare, returnează <code>True</code>.

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

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

Funcția <code>succesor(sir, n, k)</code> primește lista <code>sir</code>, reprezentând submulțimea de <code>k</code> elemente din mulțimea {1,2,...,n}, și returnează succesorul lexicografic al acestei submulțimi, adică următoarea submulțime de <code>k</code> 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 <code>i</code> pentru care <code>sir[i]</code> nu este egal cu <code>n - k + i + 1</code>. Dacă se găsește o astfel de poziție, se incrementează <code>sir[i]</code> 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 <code>if __name__ == '__main__':</code>, se citesc valorile <code>n</code> și <code>k</code>, se verifică dacă sunt valide folosind funcțiile <code>verificare_n</code> și <code>verificare_nr_elemente</code>, apoi se citește lista <code>elem</code> ș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.