Editing 2837 - Intervale5

Sursa: [https://www.pbinfo.ro/probleme/2837/intervale5 - 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.
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
# 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)


</syntaxhighlight>

==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'''.