2796 - Secvente Neuniforme: Diferență între versiuni
Fără descriere a modificării |
Fără descriere a modificării |
||
Linia 73: | Linia 73: | ||
if __name__ == '__main__': | if __name__ == '__main__': | ||
# Citim datele din fișierul de intrare | # Citim datele din fișierul de intrare | ||
with open('in | with open('secventapara.in', 'r') as f: | ||
sir = list(map(int, f.readline().split())) | sir = list(map(int, f.readline().split())) | ||
Linia 84: | Linia 84: | ||
lungime_maxima = rezolvare(sir) | lungime_maxima = rezolvare(sir) | ||
# Scriem rezultatul în fișierul de ieșire | # Scriem rezultatul în fișierul de ieșire | ||
with open('out | with open('secventeneuniforme.out', 'w') as f: | ||
print("Datele sunt introduse corect.") | print("Datele sunt introduse corect.") | ||
f.write(str(lungime_maxima)) | f.write(str(lungime_maxima)) |
Versiunea de la data 24 martie 2023 16:47
Cerinţa
Numim secvență neuniformă a unui șir de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, cu proprietatea că oricare trei termeni aflați pe poziții consecutive sunt diferiți. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Se dă un șir de cel mult 10^6 numere naturale din intervalul [0,9], în care există cel puțin trei termeni diferiți pe poziții consecutive. Se cere să se afișeze lungimea maximă a unei secvențe neuniforme a șirului dat.
Date de intrare
Fișierul de intrare secventeneuniforme.in conține un șir de cel mult 10^6 numere naturale din intervalul [0,9] separate prin spații.
Date de ieșire
Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.",fișierul de ieșire secventeneuniforme.out va conține pe prima linie lungimea maximă a unei secvențe neuniforme a șirului aflat în fișierul de intrare. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".
= Restricţii şi precizări
- Proiectați un algoritm eficient din punctul de vedere al spațiului de memorie utilizat şi al timpului de executare:
- se recomandă o soluție care să nu memoreze elementele șirului într-un tablou sau altă structură de date similară.
Exemple
Exemplul 1
- secventapara.in
- 7 7 1 3 7 7 5 3 3 3 7 8 9
- Ecran
- Datele sunt introduse corect.
- secventapara.out
- 4
Exemplul 2
- secventeneuniforme.in
- 2 2 2 2 2 2 2 2 2 2 2 2 2
- Ecran
- Datele nu corespund restricțiilor impuse.
- secventeneuniforme.out
- 0
Exemplul 3
- secventeneuniforme.in
Datele nu corespund restricțiilor impuse.
- 1 1 1 2 3 3 3 3 3 3 2 2 2 1 1 1 2 2 2 2
- secventeneuniforme.out
- 3
Rezolvare
# 2796 - Secvente Neuniforme
def validare_date_intrare(sir):
'''
Verifică dacă datele din fișierul de intrare corespund cerințelor impuse.
'''
if len(sir) == 0:
return False
for i in range(len(sir) - 2):
if sir[i] != sir[i + 1] and sir[i + 1] != sir[i + 2] and sir[i] != sir[i + 2]:
return True
return False
def rezolvare(sir):
'''
Găsește lungimea maximă a unei secvențe neuniforme în șirul dat.
'''
lungime_maxima = 0
lungime_curenta = 0
for i in range(len(sir) - 2):
if sir[i] != sir[i + 1] and sir[i + 1] != sir[i + 2] and sir[i] != sir[i + 2]:
lungime_curenta += 1
else:
if lungime_curenta > lungime_maxima:
lungime_maxima = lungime_curenta
lungime_curenta = 0
if lungime_curenta > lungime_maxima:
lungime_maxima = lungime_curenta
return lungime_maxima + 2
if __name__ == '__main__':
# Citim datele din fișierul de intrare
with open('secventapara.in', 'r') as f:
sir = list(map(int, f.readline().split()))
# Validăm datele de intrare
if not validare_date_intrare(sir):
print("Datele nu corespund restricțiilor impuse.")
exit()
# Rezolvăm problema și afișăm rezultatul
lungime_maxima = rezolvare(sir)
# Scriem rezultatul în fișierul de ieșire
with open('secventeneuniforme.out', 'w') as f:
print("Datele sunt introduse corect.")
f.write(str(lungime_maxima))