0184 - Interval 1: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: == Cerinta == Se dă un şir de n numere întregi şi un număr k. Să se determine intervalul [a,b] de lungime minimă care conţine cel puţin k elemente din sir. == Date de intrare == Fişierul de intrare interval1.txt conţine pe prima linie numerele n şi k, iar pe următoarele linii n numere întregi separate prin spaţii, reprezentând elementele şirului. == Date de iesire == Fişierul de ieşire interval1.txt va conţine pe prima linie două numere a şi b, sepa...
 
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Cerinta ==
== Cerinta ==


Se dă un şir de n numere întregi şi un număr k. Să se determine intervalul [a,b] de lungime minimă care conţine cel puţin k elemente din sir.
Se dă un şir de '''n'''' numere întregi şi un număr '''k'''. Să se determine intervalul '''[a,b]''' de lungime minimă care conţine cel puţin '''k''' elemente din sir.


== Date de intrare ==
== Date de intrare ==


Fişierul de intrare interval1.txt conţine pe prima linie numerele n şi k, iar pe următoarele linii n numere întregi separate prin spaţii, reprezentând elementele şirului.
Fişierul de intrare '''interval1i.txt''' conţine pe prima linie numerele '''n''' şi '''k''', iar pe următoarele linii '''n''' numere întregi separate prin spaţii, reprezentând elementele şirului.


== Date de iesire ==
== Date de iesire ==


Fişierul de ieşire interval1.txt va conţine pe prima linie două numere a şi b, separate printr-un spaţiu, cu semnificaţia de mai sus.
Fişierul de ieşire '''interval1out.txt''' va conţine pe prima linie două numere '''a''' şi '''b''', separate printr-un spaţiu, cu semnificaţia de mai sus.


== Restrictii si precizari ==
== Restrictii si precizari ==


*1 ≤ k ≤ n ≤ 1000
*'''1 ⩽ k ⩽ n ⩽ 1000'''
*elementele şirului aparţin intervalului [-1000,1000] şi pot fi dispuse în fişierul de intrare pe mai multe linii
*elementele şirului aparţin intervalului [-1000,1000] şi pot fi dispuse în fişierul de intrare pe mai multe linii
*dacă există mai multe intervale [a,b] de lungime minimă care conţin cel puţin k elemente din sir se va alege acela pentru care a este minim
*dacă există mai multe intervale [a,b] de lungime minimă care conţin cel puţin k elemente din sir se va alege acela pentru care a este minim
*a ≤ b
*'''a ≤ b'''


== Exemplul 1 ==
== Exemplul 1 ==
;Intrare
;interval1in.txt
:10 3
:10 3
:11 9 3 2 8 11 9 10 15 13  
:11 9 3 2 8 11 9 10 15 13  
;Iesire
;interval1out.txt
;Datele introduse corespund restrictiilor impuse
:Datele introduse corespund restrictiilor impuse
:8 9
:8 9


== Exemplul 2 ==
== Exemplul 2 ==
;Intrare
;interval1in.txt
:4 2
:4 2
:20,5,100,75.2
:20,5,100,75.2
;Iesire
 
;Datele introduse nu corespund restrictiilor impuse
:Datele introduse nu corespund restrictiilor impuse




== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
<syntaxhighlight lang="python3" line="1">
def gaseste_interval_minim(sir, n, k):
def gaseste_interval(n, k, sir):
     a = b = 0 # Pointer-ele pentru intervalul minim [a, b]
     index_start = 0
     numere_gasite = 0  # Numărul de elemente găsite în interval
     index_end = k - 1
 
     sir.sort()
     # Inițializează un dicționar pentru a număra de câte ori apare fiecare element în interval
    frecventa_elemente = {}
 
    while b < n:
        # Extinde intervalul spre dreapta
        frecventa_elemente[sir[b]] = frecventa_elemente.get(sir[b], 0) + 1
        if frecventa_elemente[sir[b]] == 1:
            numere_gasite += 1
 
        # Dacă am găsit cel puțin k elemente, încercăm să restrângem intervalul spre stânga
        while numere_gasite >= k:
            # Verificăm dacă este intervalul minim și actualizăm rezultatul
            if b - a < b_min - a_min:
                a_min, b_min = a, b


            # Încercăm să restrângem intervalul spre stânga
    lungime_minima = sir[index_end] - sir[index_start]
            frecventa_elemente[sir[a]] -= 1
    interval_minim = (sir[index_start], sir[index_end])
            if frecventa_elemente[sir[a]] == 0:
                numere_gasite -= 1
            a += 1


         # Extinde intervalul spre dreapta
    for i in range(1, n - k + 1):
         b += 1
         lungime_curenta = sir[i + k - 1] - sir[i]
         if lungime_curenta < lungime_minima:
            lungime_minima = lungime_curenta
            index_start = i
            index_end = i + k - 1
            interval_minim = (sir[index_start], sir[index_end])


     return a_min, b_min
     return interval_minim


def main():
# Citire din fișierul de intrare
    with open("interval1.txt", "r") as f_in:
with open('interval1i.txt', 'r') as file:
        # Citim numărul de elemente și k
    n, k = map(int, file.readline().split())
        n, k = map(int, f_in.readline().split())
    sir = []
    for _ in range(n):
        sir.extend(map(int, file.readline().split()))


        # Citim șirul de numere
# Apelare funcție
        sir = list(map(int, f_in.readline().split()))
rezultat = gaseste_interval(n, k, sir)


    # Găsim intervalul minim
# Scriere în fișierul de ieșire
     a, b = gaseste_interval_minim(sir, n, k)
with open('interval1out.txt', 'w') as file:
     file.write(f"{rezultat[0]} {rezultat[1]}")


    # Scriem rezultatul în fișierul de ieșire
# Verificare restrictii
    with open("interval1.txt", "w") as f_out:
assert 1 <= k <= n <= 1000
        f_out.write(f"{a} {b}\n")
assert all(-1000 <= x <= 1000 for x in sir)


if __name__ == "__main__":
    main()


</syntaxhighlight>
</syntaxhighlight>

Latest revision as of 12:19, 29 December 2023

Cerinta[edit]

Se dă un şir de n' numere întregi şi un număr k. Să se determine intervalul [a,b] de lungime minimă care conţine cel puţin k elemente din sir.

Date de intrare[edit]

Fişierul de intrare interval1i.txt conţine pe prima linie numerele n şi k, iar pe următoarele linii n numere întregi separate prin spaţii, reprezentând elementele şirului.

Date de iesire[edit]

Fişierul de ieşire interval1out.txt va conţine pe prima linie două numere a şi b, separate printr-un spaţiu, cu semnificaţia de mai sus.

Restrictii si precizari[edit]

  • 1 ⩽ k ⩽ n ⩽ 1000
  • elementele şirului aparţin intervalului [-1000,1000] şi pot fi dispuse în fişierul de intrare pe mai multe linii
  • dacă există mai multe intervale [a,b] de lungime minimă care conţin cel puţin k elemente din sir se va alege acela pentru care a este minim
  • a ≤ b

Exemplul 1[edit]

interval1in.txt
10 3
11 9 3 2 8 11 9 10 15 13
interval1out.txt
Datele introduse corespund restrictiilor impuse
8 9

Exemplul 2[edit]

interval1in.txt
4 2
20,5,100,75.2
Datele introduse nu corespund restrictiilor impuse


Rezolvare[edit]

<syntaxhighlight lang="python3" line="1"> def gaseste_interval(n, k, sir): 

   index_start = 0
   index_end = k - 1
   sir.sort()

   lungime_minima = sir[index_end] - sir[index_start]
   interval_minim = (sir[index_start], sir[index_end])

   for i in range(1, n - k + 1):
       lungime_curenta = sir[i + k - 1] - sir[i]
       if lungime_curenta < lungime_minima:
           lungime_minima = lungime_curenta
           index_start = i
           index_end = i + k - 1
           interval_minim = (sir[index_start], sir[index_end])

   return interval_minim
  1. Citire din fișierul de intrare

with open('interval1i.txt', 'r') as file: 

   n, k = map(int, file.readline().split())
   sir = []
   for _ in range(n):
       sir.extend(map(int, file.readline().split()))
  1. Apelare funcție

rezultat = gaseste_interval(n, k, sir)

  1. Scriere în fișierul de ieșire

with open('interval1out.txt', 'w') as file: 

   file.write(f"{rezultat[0]} {rezultat[1]}")
  1. Verificare restrictii

assert 1 <= k <= n <= 1000 assert all(-1000 <= x <= 1000 for x in sir)


</syntaxhighlight>

Explicatie[edit]

Intervalul [8,9] conţine 3 elemente ale şirului – 8 9 9 şi are lungimea minimă. Există încă un interval cu aceeaşi lungime care conţine 3 elemente din şir – [9,10] elemente dar 8<9.

Retrieved from "http://wiki.universitas.ro/index.php?title=0184_-_Interval_1&oldid=8673"