Vizualizare sursă pentru „0742 - Numar 2”

== Cerința ==
Fie un număr natural a având n cifre. Scrieţi un program care să determine un număr natural x cu proprietatea că este cel mai mic număr mai mare decât a, care are exact aceleaşi cifre ca şi numărul a.

== Date de intrare ==
Fișierul de intrare numar2in.tx conține două linii:

* pe prima linie un număr natural reprezentând valoarea lui n; <br>
* pe a doua linie, fără spaţii între ele, n cifre reprezentând numărul a.

== Date de ieșire ==
Fișierul de ieșire numar2out.txt va conține o singură linie pe care se va afla numărul x.

== Restricții și precizări ==
* 1 &les; '''n''' &les; 5.000.000
* pentru '''50%''' din teste, '''n''' &les; 1.000.000
* pentru toate datele de test există soluţie.

== Exemplul 1 ==
; Intrare
; numar2in.txt
: 6
: 204924
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; numar2out.txt
: 204942

=== Explicație ===
Există mai multe numere formate din exact aceleaşi cifre ca şi numărul 204924 mai mari decât el. Dintre acestea, 204942 este cel mai mic.

== Exemplul 2 ==
; Intrare
; numar2in.txt
: 6
: 2049241
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
#0742 - Numar2

def valideaza_input(n, a):
    if not (1 <= n <= 5000000):
        return False

    if len(str(a)) != n:
        return False

    return True


def gaseste_permutare_urmatoare(a):
    a = list(str(a))
    n = len(a)

    # Găsim cea mai mică cifră care poate fi schimbată
    i = n - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1

    # Dacă nu există o astfel de cifră, atunci a este cel mai mare și nu există soluție
    if i == -1:
        return None

    # Găsim cea mai mică cifră mai mare decât a[i] în partea dreaptă
    j = n - 1
    while a[j] <= a[i]:
        j -= 1

    # Schimbăm a[i] cu a[j]
    a[i], a[j] = a[j], a[i]

    # Inversăm cifrele de la i+1 la sfârșit
    a[i + 1:] = reversed(a[i + 1:])

    return int(''.join(a))


def main():
    with open("numar2in.txt", "r") as file:
        n = int(file.readline().strip())
        a = int(file.readline().strip())

    if valideaza_input(n, a):
        print("Datele de intrare corespund restricțiilor impuse")

        rezultat = gaseste_permutare_urmatoare(a)

        with open("numar2out.txt", "w") as file_out:
            file_out.write(str(rezultat))
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)


if __name__ == "__main__":
    main()

</syntaxhighlight>