2812 - Progresie3

Sursa: - Progresie3

---

Cerinţa

Un șir de numere este o progresie aritmetică de rație r dacă oricare termen al său, cu excepția primului, se obține din cel care îl precede, prin adunarea la acesta a numărului r. Exemplu: șirul 12, 14, 16, 18, 20 este o progresie de rație 2.

Se dă un șir de cel mult 1.000.000 numere naturale din intervalul [0,1.000]. Se cere să se verifice dacă există un număr natural r, astfel încât toate numerele distincte din șir să poată fi rearanjate, pentru a forma o progresie aritmetică de rație r. Se afișează numărul r, sau mesajul NU, dacă nu există un astfel de număr.

Date de intrare

Fișierul de intrare progresie3.in conține cel mult 1.000.000 numere naturale din intervalul [0,1.000], separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi in fişierul e ieșire progresie3.out va conține pe prima linie numărul r, sau mesajul NU, dacă nu există un astfel de număr. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• în șirul dat există cel puțin două valori distincte
• proiectați un algoritm eficient din punctul de vedere al timpului de executare.

Exemple

Exemplul 1

progresie3.in

180 30 80 280 130 330 230 30 30 330 80

Ieșire

Datele sunt corecte.

progresie3.out

50

Exemplul 2

progresie3.in

1 2 3 4 6

Ieșire

Datele sunt corecte.

progresie3.out

NU

Exemplul 3

progresie3.in

100 100 100

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

# 2812 Progresie3

def progresie(vector):
    f = open("progresie3.out", "w")
    ratie = int()
    vector.sort()
    r = int()
    for i in range(len(vector) - 1):
        if vector[i] != vector[i + 1]:
            ratie = vector[i + 1] - vector[i]
            r = ratie
            break
    for i in range(len(vector) - 1):
        if vector[i] != vector[i + 1]:
            ratie = vector[i + 1] - vector[i]
            if ratie != r:
                f.write("NU")
                exit()
    f.write(str(r))


def conform_restrictiilor():
    vector = list()
    with open('progresie3.in') as f:
        lines = f.readlines()
        for line in lines:
            for c in line.split():
                if c.isdigit() == True:
                    vector.append(int(c))
    if len(vector) > 1000000 or vector.count(vector[0]) == len(vector):
        print("Datele nu sunt comform restricțiilor impuse.")
        exit()
    for x in vector:
        if x < 0 or x > 1000:
            print("Datele nu sunt comform restricțiilor impuse.")
            exit()
    print("Datele sunt corecte.")
    return vector


if __name__ == '__main__':
    vector = conform_restrictiilor()
    progresie(vector)

Explicaţie cod

Funcția progresie(vector) primește un vector ca parametru și începe prin a deschide un fișier progresie3.out pentru a scrie rezultatul. Apoi, initializează două variabile ratie și r cu valoarea 0. Vectorul este sortat și apoi se parcurge prin el. Dacă două elemente consecutive sunt diferite, se calculează diferența dintre ele și se stochează în variabila ratie. De asemenea, valoarea acestei diferențe este stochează și în variabila r. Programul se oprește din parcurgerea vectorului la primul astfel de caz, deoarece nu mai este nevoie să verifice restul elementelor din vector.

După ce r a fost calculat, se parcurge din nou vectorul, de data aceasta pentru a verifica dacă toate diferențele dintre elementele consecutive ale vectorului sunt egale cu r. Dacă acest lucru este adevărat pentru toate diferențele, programul scrie valoarea r în fișierul de ieșire progresie3.out. Dacă se găsește o diferență care nu este egală cu r, programul afișează NU și se oprește prin apelul funcției exit().

Funcția conform_restrictiilor() primește ca input datele din fișierul progresie3.in și verifică dacă ele corespund restricțiilor impuse. Mai precis, datele din fișier trebuie să conțină între 2 și 1000000 de elemente și fiecare element trebuie să fie între 0 și 1000. De asemenea, toate elementele din vector trebuie să fie diferite. Dacă restricțiile nu sunt îndeplinite, programul afișează un mesaj corespunzător și se oprește prin apelul funcției exit().

În funcția main(), se apelează mai întâi funcția conform_restrictiilor() pentru a verifica dacă datele din fișier sunt valide și pentru a obține vectorul de numere. Apoi, se apelează funcția progresie(vector) pentru a determina dacă vectorul este o progresie aritmetică și pentru a afișa diferența în fișierul de ieșire sau NU, după caz.