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

<syntaxhighlight lang="python" line>

1. 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>