Bonte Lucas Gabriel at 21:24, 27 November 2023

2023-11-27T21:24:54Z

← Older revision		Revision as of 21:24, 27 November 2023
Line 7:		Line 7:
	==Date de intrare==		==Date de intrare==

	Fișierul de intrare '''~~intervale4~~.in''' conține pe prima linie numărul '''n''', iar următoarele '''n''' linii câte două valori '''x y''', reprezentând intervalele inițiale, în ordine.		Fișierul de intrare '''intervale4in.txt''' conține pe prima linie numărul '''n''', iar următoarele '''n''' linii câte două valori '''x y''', reprezentând intervalele inițiale, în ordine.

	==Date de ieșire==		==Date de ieșire==

	Fișierul de ieșire '''~~intervale4~~.~~out~~''' va conține pe prima linie numărul '''C''' de intervale din șir, după realizarea operațiilor.		Fișierul de ieșire '''intervale4out.txt''' va conține pe prima linie numărul '''C''' de intervale din șir, după realizarea operațiilor.

	==Restricții și precizări==		==Restricții și precizări==
Line 18:		Line 18:
	*pentru fiecare interval dat, '''x ≤ y''', valori întregi care se pot reprezenta pe patru octeți.		*pentru fiecare interval dat, '''x ≤ y''', valori întregi care se pot reprezenta pe patru octeți.

	==~~Exemplu~~:==		==Exemplul 1:==

	'''~~intervale4~~.in'''		'''intervale4in.txt'''

	:5		5
	:2 3		2 3
	:4 6		4 6
	:3 5		3 5
	:8 10		8 10
	:7 11		7 11

	'''~~intervale4~~.~~out~~'''		'''intervale4out.txt'''

	:2		Datele de intrare corespund restrictiilor impuse
			2

			==Exemplul 2:==

			'''intervale4in.txt'''

			intervale4

			'''intervale4out.txt'''

			Datele de intrare nu corespund restrictiilor impuse

	==Rezolvare==		==Rezolvare==
Line 37:		Line 48:
	<syntaxhighlight lang="python" line="1" start="1">		<syntaxhighlight lang="python" line="1" start="1">

	def solve(n, intervals):		def validare(numere, intervals): # functia de validare a datelor de intrare

			if numere < 1 or numere > 100000:
			raise ValueError

			for intervall in intervals:
			if len(intervall) != 2 or intervall[0] > intervall[1]:
			raise ValueError

			file_out.write("Datele de intrare corespund restrictiilor impuse\n")


			def solve(intervals): # functia de rezolvare
	# Sortăm intervalele în ordine crescătoare		# Sortăm intervalele în ordine crescătoare
	intervals.sort()		intervals.sort()

	# Inițializăm lista de intervale unite cu primul interval		# Inițializăm lista de intervale unite cu primul interval
	~~merged~~ = [intervals[0]]		unite = [intervals[0]]

	# Parcurgem fiecare interval		# Parcurgem fiecare interval
	for ~~current~~ in intervals:		for curent in intervals:
	# Obținem ultimul interval adăugat în lista de intervale unite		# Obținem ultimul interval adăugat în lista de intervale unite
	~~last~~ = ~~merged~~[-1]		ultim = unite[-1]

	# Dacă intervalul curent se intersectează cu ultimul interval adăugat		# Dacă intervalul curent se intersectează cu ultimul interval adăugat
	if ~~current~~[0] <= ~~last~~[1]:		if curent[0] <= ultim[1]:
	# Actualizăm capătul drept al ultimului interval cu valoarea maximă dintre capetele drepte ale celor două intervale		# Actualizăm capătul drept al ultimului interval cu valoarea maximă dintre capetele drepte ale celor două intervale
	~~last~~[1] = max(~~last~~[1], ~~current~~[1])		ultim[1] = max(ultim[1], curent[1])
	else:		else:
	# Dacă nu se intersectează, adăugăm intervalul curent în lista de intervale unite		# Dacă nu se intersectează, adăugăm intervalul curent în lista de intervale unite
	~~merged~~.append(~~current~~)		unite.append(curent)

	# Returnăm numărul de intervale din lista de intervale unite		# Returnăm numărul de intervale din lista de intervale unite
	return len(~~merged~~)		return len(unite)


			if __name__ == '__main__':
			file_in = open("intervale4in.txt", "r") # declararea fisierelor
			file_out = open("intervale4out.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

			# din cauza datelor de intrare pot aparea 2 tipuri de erori, valueError sau IndexError pe care le tratam
			try:
			n = int(file_in.readline()) # citirea numarului de intervale
			intervale = []
			for _ in range(n):
			interval = list(map(int, file_in.readline().split()))
			intervale.append(interval)

			validare(n, intervale) # apelul functiei de validare
			file_out.write(str(solve(intervale))) # apelul functiei de rezolvare

	~~# Definim numărul~~ de ~~intervale și intervalele inițiale~~		except ValueError:
	~~n = 5~~		file_out.write("Datele de intrare nu corespund restrictiilor impuse")
	~~intervals = [[2, 3], [4, 6], [3, 5], [8, 10], [7, 11]]~~		except IndexError:
			file_out.write("Datele de intrare nu corespund restrictiilor impuse")

	~~# Apelăm funcția solve cu aceste valori și afișăm rezultatul pe ecran~~		file_in.close()
	~~print(solve~~(~~n, intervals)~~)		file_out.close()

	</syntaxhighlight>		</syntaxhighlight>

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră un șir de '''n''' intervale închise întregi. Două intervale consecutive în șir care au intersecția nevidă se reunesc și se înlocuiesc în șir cu intervalul reuniune. Operația se repetă până când nu mai sunt în șir două intervale consecutive cu intersecția nevidă. Să se determine câte intervale există în șir după realizarea acestor operații. ==Date de intrare== Fișierul de intrare '''intervale4.in''' conține pe prima...

2023-10-30T14:27:02Z

Pagină nouă: ==Cerința== Se consideră un șir de '''n''' intervale închise întregi. Două intervale consecutive în șir care au intersecția nevidă se reunesc și se înlocuiesc în șir cu intervalul reuniune. Operația se repetă până când nu mai sunt în șir două intervale consecutive cu intersecția nevidă. Să se determine câte intervale există în șir după realizarea acestor operații. ==Date de intrare== Fișierul de intrare '''intervale4.in''' conține pe prima...

New page

==Cerința==

Se consideră un șir de '''n''' intervale închise întregi. Două intervale consecutive în șir care au intersecția nevidă se reunesc și se înlocuiesc în șir cu intervalul reuniune. Operația se repetă până când nu mai sunt în șir două intervale consecutive cu intersecția nevidă.

Să se determine câte intervale există în șir după realizarea acestor operații.

==Date de intrare==

Fișierul de intrare '''intervale4.in''' conține pe prima linie numărul '''n''', iar următoarele '''n''' linii câte două valori '''x y''', reprezentând intervalele inițiale, în ordine.

==Date de ieșire==

Fișierul de ieșire '''intervale4.out''' va conține pe prima linie numărul '''C''' de intervale din șir, după realizarea operațiilor.

==Restricții și precizări==

*'''1 ≤ n ≤ 100.000;'''
*pentru fiecare interval dat, '''x ≤ y''', valori întregi care se pot reprezenta pe patru octeți.

==Exemplu:==

'''intervale4.in'''

:5
:2 3
:4 6
:3 5
:8 10
:7 11

'''intervale4.out'''

:2

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def solve(n, intervals):
# Sortăm intervalele în ordine crescătoare
intervals.sort()

# Inițializăm lista de intervale unite cu primul interval
merged = [intervals[0]]

# Parcurgem fiecare interval
for current in intervals:
# Obținem ultimul interval adăugat în lista de intervale unite
last = merged[-1]

# Dacă intervalul curent se intersectează cu ultimul interval adăugat
if current[0] <= last[1]:
# Actualizăm capătul drept al ultimului interval cu valoarea maximă dintre capetele drepte ale celor două intervale
last[1] = max(last[1], current[1])
else:
# Dacă nu se intersectează, adăugăm intervalul curent în lista de intervale unite
merged.append(current)

# Returnăm numărul de intervale din lista de intervale unite
return len(merged)

# Definim numărul de intervale și intervalele inițiale
n = 5
intervals = [[2, 3], [4, 6], [3, 5], [8, 10], [7, 11]]

# Apelăm funcția solve cu aceste valori și afișăm rezultatul pe ecran
print(solve(n, intervals))

</syntaxhighlight>

==Explicație==

Intervalele din șirul inițial sunt: '''[2,3] [4,6] [3,5] [8,10] [7,11].'''

1.Se reunesc intervalele '''[4,6] [3,5]''' și se obține șirul '''[2,3] [3,6] [8,10] [7,11].'''
2.Se reunesc intervalele '''[2,3] [3,6]''' și se obține șirul '''[2,6] [8,10] [7,11].'''
3.Se reunesc intervalele '''[8,10] [7,11]''' și se obține șirul '''[2,6] [7,11].'''
La final în șir se află două intervale.

0878 - Intervale4 - Revision history

Bonte Lucas Gabriel at 21:24, 27 November 2023