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

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 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 = list(map(int, file.readline().strip()))

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

</syntaxhighlight>