Editing 3273 - cmmdcsecv

Sursa: [https://www.pbinfo.ro/probleme/3273/cmmdcsecv 3273 - cmmdcsecv]
----


== Cerinţa ==
Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din 
șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1.

Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvență este strict mai mare decât 1.


== Date de intrare ==
Fișierul de intrare cmmdcsecv.in conține pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.


== Date de ieșire == 

Dacă datele sunt introduse corect, pe ecran se va afișa: 
'''"Datele sunt introduse corect."''' cmmdcsecv.out va conține pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.'', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

== Restricţii şi precizări ==
* 3 ≤ n ≤ 100.000
* 1 ≤ ai ≤ 1000, pentru orice 1 ≤ i ≤ n
== Exemplu 1 ==
; Intrare
: cmmdcsecv.in
: 6
: 15 28 14 56 42 5
; Ieșire
: Datele sunt introduse correct.
: cmmdcsecv.out
: 4

== Exemplu 1 ==
; Intrare
: cmmdcsecv.in
: -6
: 23 5 7 15 28 14 56 42 5
; Ieșire
: Datele nu corespund restricțiilor impuse.


== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3273 - cmmdcsecv

def calculate_gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def find_longest_sequence(n, nums):
    max_length = 0
    current_length = 0

    for i in range(n):
        for j in range(i, n):
            valid = True
            for k in range(i, j + 1):
                if calculate_gcd(nums[k], nums[k + 1]) == 1:
                    valid = False
                    break
            if valid:
                current_length = j - i + 1
                max_length = max(max_length, current_length)

    return max_length


def validate_input(n, nums):
    if n < 3 or n > 100000 or len(nums) != n or any(num < 1 or num > 1000 for num in nums):
        return False
    return True


if __name__ == "__main__":
    with open("cmmdcsecv.in", "r") as file:
        n = int(file.readline())
        nums = list(map(int, file.readline().split()))

    if validate_input(n, nums):
        print("Datele sunt introduse corect.")
        result = find_longest_sequence(n, nums)
        with open("cmmdcsecv.out", "w") as file:
            file.write(str(result))
    else:
        print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>
== Explicatie Rezolvare ==
calculate_gcd(a, b): Această funcție primește două numere a și b și calculează cel mai mare divizor comun (CMMD) folosind algoritmul lui Euclid. Returnează rezultatul CMMD.

find_longest_sequence(n, nums): Această funcție primește un număr n reprezentând lungimea șirului și o listă nums care conține elementele șirului. Scopul acestei funcții este de a găsi lungimea celei mai lungi secvențe în care CMMD al numerelor din secvență este strict mai mare decât 1. Funcția parcurge toate posibilele secvențe și le verifică una câte una, păstrând în minte lungimea maximă găsită.

validate_input(n, nums): Această funcție primește un număr n reprezentând lungimea șirului și o listă nums cu elementele șirului. Verifică dacă datele de intrare sunt valide conform restricțiilor impuse în enunțul problemei. Returnează True dacă datele sunt valide și False în caz contrar.

Blocul if __name__ == "__main__": În acest bloc se efectuează citirea datelor de intrare din fișierul "cmmdcsecv.in". Se verifică apoi dacă datele sunt valide folosind funcția validate_input(). Dacă datele sunt valide, se afișează mesajul "Datele sunt introduse corect." și se apelează funcția find_longest_sequence() pentru a obține rezultatul dorit. Rezultatul este apoi scris în fișierul "cmmdcsecv.out". Dacă datele nu sunt valide, se afișează mesajul "Datele nu corespund restricțiilor impuse."