2100 - Prod Nr
Enunţ
Se consideră o succesiune de numere naturale a[1] a[2] ... a[N]. Cu aceste numere se construieşte un şir de caractere astfel: pentru fiecare număr a[i] din şir (i=1, 2, ..., N) se scrie mai întâi numărul de cifre ale lui a[i], apoi cifrele lui a[i].
Cerința
Scrieţi un program care pe baza şirului de caractere să determine câte numere sunt în succesiune, precum şi descompunerea în factori primi a produsului numerelor din succesiune.
Date de intrare
Fişierul de intrare prodnr.in conţine pe prima linie şirul de caractere.
Date de ieșire
Fişierul de ieşire prodnr.out va conţine pe prima linie numărul natural N, reprezentând numărul de numere din succesiune. Pe următoarele linii va fi scrisă descompunerea în factori primi a produsului celor N numere din succesiune. Pe fiecare linie vor fi scrise două numere naturale separate printr-un singur spaţiu f m, unde f reprezintă factorul prim, iar m multiplicitatea acestuia în produs. Factorii primi vor fi afişaţi în fişier în ordine strict crescătoare.
Restricții și precizări
- Lungimea şirului este de cel mult 30.000;
- Numerele din succesiune sunt nenule şi au cel mult 5 cifre.
- Produsul numerelor este strict mai mare decât 1.
Exemplu 1
- prodnr.in
- 410242253100213235
- prodnr.out
- 5
- 2 12
- 5 5
- 7 1
- 13 1
Explicație
Numerele sunt: 1024 25 100 13 35
Exemplu 2
- prodnr.in
- 12a34b
- prodnr.out
- Date de intrare invalide!
Rezolvare
#2100 ProdNr
def descompunere_in_factori_primi(n):
factori = {}
divizor = 2
while n > 1:
if n % divizor == 0:
if divizor not in factori:
factori[divizor] = 1
else:
factori[divizor] += 1
n //= divizor
else:
divizor += 1
return factori
def verifica_date_intrare(sir):
if not sir:
return False
for caracter in sir:
if not caracter.isdigit():
return False
return True
def main():
# Citirea şirului de caractere
with open("prodnr.in", "r") as fin:
sir = fin.readline().strip()
# Verificarea datelor de intrare
if not verifica_date_intrare(sir):
# Scrierea mesajului de date invalide în fișierul de ieșire
with open("prodnr.out", "w") as fout:
fout.write("Date de intrare invalide!")
return
# Extrage numerele din şir
numere = []
i = 0
while i < len(sir):
lungime_numar = int(sir[i])
numar = int(sir[i + 1:i + 1 + lungime_numar])
numere.append(numar)
i += 1 + lungime_numar
# Calculul numărului de numere din succesiune
N = len(numere)
# Calculul produsului numerelor din succesiune
produs = 1
for numar in numere:
produs *= numar
# Calculul descompunerii în factori primi a produsului
descompunere = descompunere_in_factori_primi(produs)
# Scrierea rezultatelor în fișierul de ieșire
with open("prodnr.out", "w") as fout:
# Scrierea numărului de numere din succesiune
fout.write(str(N) + "\n")
# Scrierea descompunerii în factori primi
for factor, multiplicitate in descompunere.items():
fout.write(f"{factor} {multiplicitate}\n")
if __name__ == "__main__":
main()