0184 - Interval 1 - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T12:19:13Z

Rezolvare

← Older revision		Revision as of 12:19, 29 December 2023
Line 67:		Line 67:
	with open('interval1out.txt', 'w') as file:		with open('interval1out.txt', 'w') as file:
	file.write(f"{rezultat[0]} {rezultat[1]}")		file.write(f"{rezultat[0]} {rezultat[1]}")

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

Mesarosdenisa: /* Rezolvare */

2023-12-27T13:06:27Z

Rezolvare

← Older revision		Revision as of 13:06, 27 December 2023
Line 36:		Line 36:
	== 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~~		lungime_minima = sir[index_end] - sir[index_start]
	~~frecventa_elemente~~ = {}		interval_minim = (sir[index_start], sir[index_end])

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

	~~# Dacă am găsit cel puțin k elemente, încercăm să restrângem intervalul spre stânga~~		return interval_minim
	~~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~~		# Citire din fișierul de intrare
	~~frecventa_elemente[sir[a]] -~~= 1		with open('interval1i.txt', 'r') as file:
	~~if frecventa_elemente[~~sir[a]~~] == 0~~:		n, k = map(int, file.readline().split())
	~~numere_gasite -= 1~~		sir = []
	~~a += 1~~		for _ in range(n):
			sir.extend(map(int, file.readline().split()))

	# ~~Extinde intervalul spre dreapta~~		# Apelare funcție
	~~b +~~= 1		rezultat = gaseste_interval(n, k, sir)

	~~return a_min, b_min~~		# Scriere în fișierul de ieșire
			with open('interval1out.txt', 'w') as file:
			file.write(f"{rezultat[0]} {rezultat[1]}")

	~~def main():~~
	~~with open("interval1.txt", "r") as f_in:~~
	~~# Citim numărul de elemente și k~~
	~~n, k = map(int, f_in.readline().split())~~

	~~# Citim șirul de numere~~
	~~sir = list(map(int, f_in.readline().split()))~~

	~~# Găsim intervalul minim~~
	~~a, b = gaseste_interval_minim(sir, n, k)~~

	~~# Scriem rezultatul în fișierul de ieșire~~
	~~with open("interval1.txt", "w") as f_out:~~
	~~f_out.write(f"{a} {b}\n")~~

	~~if __name__ == "__main__":~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa at 13:05, 27 December 2023

2023-12-27T13:05:20Z

← Older revision		Revision as of 13:05, 27 December 2023
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 &les; k &les; n &les; 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

Mesarosdenisa: 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...

2023-12-13T12:32:28Z

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

New page

== 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, separate printr-un spaţiu, cu semnificaţia de mai sus.

== Restrictii si precizari ==

*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 ==
;Intrare
:10 3
:11 9 3 2 8 11 9 10 15 13
;Iesire
;Datele introduse corespund restrictiilor impuse
:8 9

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def gaseste_interval_minim(sir, n, k):
a = b = 0 # Pointer-ele pentru intervalul minim [a, b]
numere_gasite = 0 # Numărul de elemente găsite în interval

# 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
frecventa_elemente[sir[a]] -= 1
if frecventa_elemente[sir[a]] == 0:
numere_gasite -= 1
a += 1

# Extinde intervalul spre dreapta
b += 1

return a_min, b_min

def main():
with open("interval1.txt", "r") as f_in:
# Citim numărul de elemente și k
n, k = map(int, f_in.readline().split())

# Citim șirul de numere
sir = list(map(int, f_in.readline().split()))

# Găsim intervalul minim
a, b = gaseste_interval_minim(sir, n, k)

# Scriem rezultatul în fișierul de ieșire
with open("interval1.txt", "w") as f_out:
f_out.write(f"{a} {b}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

== Explicatie ==

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.