2837 - Intervale5

Sursa: - Intervale5

---

Cerinţa

Se dă un șir de cel mult 1.000.000 de numere naturale din intervalul [0,100]. Se cere să se determine toate perechile distincte formate din termeni ai șirului dat, x și y (y-x≥2), astfel încât să nu existe niciun termen al șirului care să aparțină intervalului (x,y). Dacă nu există nicio astfel de pereche, se afișează mesajul "nu exista".

Date de intrare

Fișierul de intrare intervale5.in conține pe prima linie elementele șirului, 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 de ieșire intervale5.out va conține perechile găsite, câte una pe linie, în ordine strict crescătoare, separate printr-un spațiu, iar dacă nu există nicio astfel de pereche, se afișează mesajul nu exista. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• pentru determinarea numerelor cerute utilizați un algoritm eficient din punctul de vedere al timpului de executare: recomandă evitarea memorării elementelor șirului într-un tablou sau în altă structură de date similară

Exemple

Exemplul 1

intervale5.in

5 9 0 8 10 11 12 13 15 14 6 7 40 10 0 0 5 41 95 7

Ieșire

Datele sunt corecte.

intervale5.out

0 5

15 40

41 95

Exemplul 2

intervale5.in

1 2 3 4 5 6

Ieșire

Datele sunt corecte.

intervale5.out

nu exista

Exemplul 3

intervale5.in

101 100 102 3000

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

# 2837 Intervale5

def intervale5(vector):
    maxi = -1
    v = [0] * 101
    for x in vector:
        v[x] = 1
        if x > maxi:
            maxi = x
    contor = 0
    f = open("intervale5.out", "w")
    for i in range(0, maxi - 1):
        for j in range(i + 2, maxi + 1):
            ok = True
            for k in range(i + 1, j):
                if v[k] == 1:
                    ok = False
            if ok and v[i] == 1 and v[j] == 1:
                line = [str(i), " ", str(j), "\n"]
                f.writelines(line)
                contor += 1
    if contor == 0:
        f.write("nu exista")


def conform_restrictiilor():
    vector = list()
    with open('intervale5.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:
        print("Datele nu sunt comform restricțiilor impuse.")
        exit()
    for x in vector:
        if x < 0 or x > 100:
            print("Datele nu sunt comform restricțiilor impuse.")
            exit()
    print("Datele sunt corecte.")
    return vector


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

Explicaţie cod

Funcția conform_restrictiilor() citește datele din fișierul intervale5.in și verifică dacă acestea sunt în concordanță cu cerințele problemei. Dacă datele nu sunt conforme, se afișează un mesaj corespunzător și se oprește execuția programului. Dacă datele sunt conforme, funcția returnează vectorul de valori citite din fișier.

Funcția intervale5(vector) primește ca parametru vectorul de valori citite din fișier și determină intervalele de lungime minimă 5 care nu conțin alte valori între ele decât cele din vector. Aceste intervale sunt afișate în fișierul intervale5.out.

Pentru a determina aceste intervale, se construiește un vector v în care valoarea 1 se asociază fiecărei valori din vectorul citit din fișier, iar valoarea 0 se asociază celorlalte valori. Se caută apoi toate perechile de indici i și j, cu proprietatea că între acești indici nu se găsesc alte valori decât cele din vectorul inițial, iar j-i este cel puțin 4. Pentru a verifica dacă între i și j se găsesc alte valori decât cele din vectorul inițial, se parcurge vectorul v între indicii i și j și se verifică dacă toate valorile sunt zero. Dacă condiția este satisfăcută, intervalul i-j este afișat în fișierul intervale5.out.