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;
  
• 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 ⩽ n ⩽ 5.000.000
• pentru 50% din teste, n ⩽ 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

#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()