1502 - Virgule

Enunt

Se considera un sir de cifre zecimale (de la 0 la 9). in acest sir trebuie sa inseram virgule, separand astfel cifrele in scopul de a forma numere.

Cerinta

Scrieti un program care sa insereze virgule in sirul de cifre astfel incat sa se obtina o secventa de numere strict crescatoare, iar ultimul numar din secventa sa fie minim.

Date de intrare

Fisierul de intrare virgule.in contine pe prima linie o secventa de cifre.

Date de iesire

Fisierul de iesire virgule.out va contine o singura linie pe care va fi scrisa secventa strict crescatoare de numere, obtinuta prin inserarea virgulelor in sirul cifrelor, secventa in care ultimul numar este minim.

Restrictii si precizari

• 0 < Lungimea secventei de cifre din fisierul de intrare < 95.
• Numerele din secventa de numere obtinuta pot incepe cu cifra 0.
• Daca exista mai multe solutii in care ultimul numar din secventa este minim, se alege secventa in care primul numar este maxim. Daca si in acest caz exista mai multe solutii, se alege solutia in care al doilea numar este maxim, s.a.m.d.
• Fisierul de intrare si fisierul de iesire nu vor contine spatii.
• Pentru teste valorand 50% din punctajul acordat pe teste fisierul de intrare nu contine cifra 0.

Exemplul 1

virgule.in

6879

virgule.out

68,79

Exemplul 2

virgule.in

16879121001

virgule.out

168,79,12,1,0,01

Exemplu 3

virgule.in

123abc45

virgule.out

Introduceți un șir valid de cifre.

Rezolvare

#1502 Virgule
def insert_commas(digits):
    n = len(digits)

    # Inițializăm o listă pentru a memora pozițiile unde inserăm virgule
    comma_positions = []

    # Adăugăm o virgulă la finalul șirului dacă este necesar
    for i in range(1, n):
        if digits[i] <= digits[i - 1]:
            comma_positions.append(i)

    # Construim secvența cu virgule
    result_with_commas = []
    start = 0

    for pos in comma_positions:
        result_with_commas.extend(map(str, digits[start:pos]))
        result_with_commas.append(',')
        start = pos

    # Adăugăm ultima grupare de cifre
    result_with_commas.extend(map(str, digits[start:]))

    # Eliminăm virgulele consecutive
    final_result = []
    for i in range(len(result_with_commas) - 1):
        if result_with_commas[i] != ',' or result_with_commas[i + 1] != ',':
            final_result.append(result_with_commas[i])

    # Adăugăm ultimul element
    final_result.append(result_with_commas[-1])

    return final_result

def validate_input(digits):
    if not digits or not all(char.isdigit() for char in digits):
        return False, "Introduceți un șir valid de cifre."

    return True, None


if __name__ == "__main__":
    # Citim șirul de cifre din fișierul de intrare
    with open("virgule.in", "r") as file:
        digits = file.readline().strip()

    # Validăm datele de intrare
    is_valid, error_message = validate_input(digits)
    if not is_valid:
        with open("virgule.out", "w", encoding="utf-8") as file_out:
            file_out.write(error_message)
        exit()

    # Calculăm și afișăm rezultatul în fișierul de ieșire
    digits = list(map(int, digits))
    result = insert_commas(digits)
    with open("virgule.out", "w", encoding="utf-8") as file_out:
        file_out.write("".join(result))