3273 - cmmdcsecv: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 16: Linia 16:
Fișierul de ieșire cmmdcsecv.out va conține:
Fișierul de ieșire cmmdcsecv.out va conține:
Dacă datele sunt introduse corect, pe ecran se va afișa:  
Dacă datele sunt introduse corect, pe ecran se va afișa:  
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''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 ==
== Restricţii şi precizări ==
* 3 ≤ n ≤ 100.000
* 3 ≤ n ≤ 100.000
* 1 ≤ ai ≤ 1000, pentru orice 1 ≤ i ≤ n
* 1 ≤ ai ≤ 1000, pentru orice 1 ≤ i ≤ n
== Exemplu ==
== Exemplu 1 ==
; Intrare
; Intrare
: cmmdcsecv.in
: 6
: 6
: 15 28 14 56 42 5
: 15 28 14 56 42 5
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: cmmdcsecv.out
: Datele sunt introduse correct.
: Datele sunt introduse correct.
: 4
: 4
== Exemplu 1 ==
; Intrare
: cmmdcsecv.in
: -6
: 23 5 7 15 28 14 56 42 5
; Ieșire
: cmmdcsecv.out
: Datele nu corespund restricțiilor impuse.


== Rezolvare ==  
== Rezolvare ==  

Versiunea de la data 3 mai 2023 08:06

Sursa: 3273 - cmmdcsecv


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.


Cerinţa

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

Fișierul de ieșire cmmdcsecv.out va conține: Dacă datele sunt introduse corect, pe ecran se va afișa: '"Datele sunt introduse corect.", apoi pe un rând nou 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
cmmdcsecv.out
Datele sunt introduse correct.
4

Exemplu 1

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


Rezolvare

Rezolvare ver. 1

# 3273 - cmmdcsecv

import math

def read_input():
    with open("cmmdcsecv.in", "r") as f:
        n = int(f.readline())
        arr = list(map(int, f.readline().split()))
    return n, arr

def cmmdcsecv(n, arr):
    max_len = 0  # lungimea maxima a secventei
    for i in range(n):
        d = arr[i]  # cel mai mare divizor comun
        for j in range(i + 1, n):
            d = math.gcd(d, arr[j])
            if d > 1:
                max_len = max(max_len, j - i + 1)
    return max_len

def validate_output(result):
    with open("cmmdcsecv.out", "r") as f:
        expected_result = int(f.readline())
    assert result == expected_result, f"Error: expected {expected_result}, but got {result}"

if __name__ == "__main__":
    n, arr = read_input()
    result = cmmdcsecv(n, arr)
    try:
        validate_output(result)
        print("Datele sunt introduse corect.")
    except AssertionError:
        print("Datele nu corespund restricțiilor impuse.")
    print(result)

Explicatie Rezolvare

Acest cod este o implementare în Python a algoritmului pentru a găsi cea mai lungă secvență a unei liste date de numere în care toate numerele din secvență au un divizor comun mai mare decât 1.

Mai exact, codul citeste datele de intrare din fișierul "cmmdcsecv.in", care conține pe prima linie numărul de elemente din lista și pe a doua linie lista în sine. Apoi, calculează lungimea maximă a unei secvențe cu numere care au un divizor comun mai mare decât 1. În final, codul verifică dacă rezultatul obținut este corect prin comparație cu rezultatul așteptat din fișierul "cmmdcsecv.out".

În această versiune modificată a codului, se verifică dacă rezultatul obținut este corect și se afișează un mesaj corespunzător în funcție de acesta. Dacă rezultatul este corect, se afișează "Datele sunt introduse corect." și se afișează lungimea secvenței. Dacă rezultatul nu este corect, se afișează "Datele nu corespund restricțiilor impuse." și se afișează lungimea secvenței.