0519 - Secventa1 - Revision history

Flaviu at 19:43, 14 May 2023

2023-05-14T19:43:11Z

← Older revision		Revision as of 19:43, 14 May 2023
Line 30:		Line 30:
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	~~: 6~~

	== Rezolvare ==		== Rezolvare ==
Line 37:		Line 37:
	# 0519 - Secventa1		# 0519 - Secventa1

	def ~~gaseste_secventa_maxima~~(x, y):		def find_sequence(x, y):
	~~for i in range(~~len(x) - len(y) + 1):
	if x[i:i+~~len(y)~~] == y:		n = len(x)
	return i + ~~1 # indexam de la~~ 1		m = len(y)
			if m > n:
			return -1
			for i in range(n - m + 1):
			if x[i:i+m] == y:
			return i + 1
	return -1		return -1

	def ~~main~~():		def validate_input(n, m):

			if not(1 <= m <= n <= 1000):
			return False
			return True

			if __name__ == '__main__':
			# Citim input-ul
	n = int(input())		n = int(input())
	x = input().split()		x = list(map(int, input().split()))
	m = int(input())		m = int(input())
	y = input().split()		y = list(map(int, input().split()))

			# Validam input-ul
			if not validate_input(n, m):
			print('Datele nu corespund restrictiilor impuse.')
			exit()

	# ~~validare date de intrare~~		# Gasim secventa si afisam raspunsul
	~~if n <= 0 or n > 1000 or m <~~= ~~0 or m > n or len~~(x~~) != n or len(~~y) != m:		poz = find_sequence(x, y)
	print("Datele ~~nu corespund restricțiilor impuse~~.")		if poz != -1:
			print('Datele sunt introduse corect.')
			print(poz)
	else:		else:
	~~try:~~		print('Datele sunt introduse corect.')
	~~x = [int(elem) for elem in x]~~		print('NU')
	~~y = [int(elem) for elem in y]~~
	~~except ValueError:~~
	~~print("Datele nu corespund restricțiilor impuse.")~~
	~~exit(0)~~

	~~if max(x) >= 1000 or max(y) >= 1000:~~
	print(~~"Datele nu corespund restricțiilor impuse.")~~
	~~else:~~
	~~pozitie_start = gaseste_secventa_maxima(x, y)~~
	~~if pozitie_start != -1:~~
	~~print("~~Datele sunt introduse corect.")
	print(~~pozitie_start~~)
	~~else:~~
	~~print("Datele nu corespund restrictiilor impuse ")~~

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



	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

			Funcția validate_input verifică restricțiile impuse și returnează True dacă datele sunt valide, sau False în caz contrar.

	~~În acest cod, funcția `read_input()` citeste valorile de intrare de la utilizator și le returnează într-o tuplă, în ordinea în care au fost citite.~~		Funcția find_subsequence caută secvența y în vectorul x și returnează poziția de început a secvenței sau -1 dacă secvența nu a fost găsită.

	Funcția ~~`is_subsequence(n, x, m,~~ y~~)` primește 4 argumente, primele două fiind lungimea și elementele listei `~~x~~`, iar ultimele două fiind lungimea și elementele listei `y`. Funcția verifică dacă lista `y` este o subsecvență a listei `x`~~ și returnează ~~indexul primului element al primei apariții~~ a ~~listei `y` în lista `x` dacă da,~~ sau `-1~~` în caz contrar~~.

	~~Funcția `validate_output(result)` primește rezultatul obținut~~ de la ~~`is_subsequence()`~~ și ~~îl afișează în funcție~~ de ~~cerințele problemei, adică afișează indexul primului element al primei apariții~~ a ~~listei `~~y` în ~~lista `~~x`, ~~dacă aceasta este o subsecvență a listei `x`, sau afișează~~ "Datele nu corespund ~~restrictiilor~~ impuse" ~~în caz contrar.~~		În funcția main citim datele de intrare și le trimitem la funcția de validare. Dacă datele sunt valide, afișăm mesajul "Datele sunt introduse corect." și apoi apelăm funcția de rezolvare pentru a găsi poziția de început a secvenței y în vectorul x. În caz contrar, afișăm mesajul "Datele nu corespund restricțiilor impuse."

Flaviu at 21:07, 13 May 2023

2023-05-13T21:07:51Z

← Older revision		Revision as of 21:07, 13 May 2023
Line 37:		Line 37:
	# 0519 - Secventa1		# 0519 - Secventa1

	def ~~validate_input~~(n, x~~, m~~, y):		def gaseste_secventa_maxima(x, y):
	~~if not (1 <= n <= 100000 and 1 <= m <= 100000):~~		for i in range(len(x) - len(y) + 1):
	~~print("Datele nu corespund restricțiilor impuse.")~~		if x[i:i+len(y)] == y:
	~~return False~~		return i + 1 # indexam de la 1
	~~if not all(1 <= xi <= 1000000~~ for xi in ~~x) or not all~~(~~1 <= yi <= 1000000 for yi in y):~~
	~~print~~(~~"Datele nu corespund restricțiilor impuse."~~)
	~~return False~~
	~~return True~~

	~~def is_subsequence~~(~~n, x, m,~~ y):
	~~for i in range(n - m~~ + 1):
	if x[i:i + m] == y:
	return i + 1
	return -1		return -1

	def ~~read_input~~():		def main():
	~~try:~~		n = int(input())
	n = int(input(~~"Introduceti numarul de elemente al vectorului x: "~~))		x = input().split()
	x = ~~list(map(int,~~ input(~~"Introduceti elementele vectorului x, separate prin spatiu: "~~).split()))		m = int(input())
	m = int(input(~~"Introduceti numarul de elemente al vectorului y: "~~))		y = input().split()
	y = ~~list(map(int,~~ input(~~"Introduceti elementele vectorului y, separate prin spatiu: "~~).split()))
	~~if not validate_input(n, x, m, y):~~
	~~print("Datele nu corespund restricțiilor impuse.")~~
	~~return None, None, None, None~~
	~~print("Datele sunt introduse corect.")~~
	~~return n, x, m, y~~
	~~except ValueError:~~
	~~print("Datele introduse trebuie sa fie numere intregi.")~~
	~~return None, None, None, None~~


	~~def validate_output(result):~~		# validare date de intrare
	if ~~result~~ != -1:		if n <= 0 or n > 1000 or m <= 0 or m > n or len(x) != n or len(y) != m:
	print(~~result~~)		print("Datele nu corespund restricțiilor impuse.")
	else:		else:
	print("NU")		try:
			x = [int(elem) for elem in x]
			y = [int(elem) for elem in y]
			except ValueError:
			print("Datele nu corespund restricțiilor impuse.")
			exit(0)

			if max(x) >= 1000 or max(y) >= 1000:
			print("Datele nu corespund restricțiilor impuse.")
			else:
			pozitie_start = gaseste_secventa_maxima(x, y)
			if pozitie_start != -1:
			print("Datele sunt introduse corect.")
			print(pozitie_start)
			else:
			print("Datele nu corespund restrictiilor impuse ")

	if __name__ == "__main__":		if __name__ == "__main__":
	~~n, x, m, y = read_input~~()		main()
	~~if n is not None and x is not None and m is not None and y is not None:~~
	~~result = is_subsequence(n, x, m, y)~~
	~~validate_output(result~~)


Line 91:		Line 83:
	Funcția `is_subsequence(n, x, m, y)` primește 4 argumente, primele două fiind lungimea și elementele listei `x`, iar ultimele două fiind lungimea și elementele listei `y`. Funcția verifică dacă lista `y` este o subsecvență a listei `x` și returnează indexul primului element al primei apariții a listei `y` în lista `x` dacă da, sau `-1` în caz contrar.		Funcția `is_subsequence(n, x, m, y)` primește 4 argumente, primele două fiind lungimea și elementele listei `x`, iar ultimele două fiind lungimea și elementele listei `y`. Funcția verifică dacă lista `y` este o subsecvență a listei `x` și returnează indexul primului element al primei apariții a listei `y` în lista `x` dacă da, sau `-1` în caz contrar.

	Funcția `validate_output(result)` primește rezultatul obținut de la `is_subsequence()` și îl afișează în funcție de cerințele problemei, adică afișează indexul primului element al primei apariții a listei `y` în lista `x`, dacă aceasta este o subsecvență a listei `x`, sau afișează "NU" în caz contrar.		Funcția `validate_output(result)` primește rezultatul obținut de la `is_subsequence()` și îl afișează în funcție de cerințele problemei, adică afișează indexul primului element al primei apariții a listei `y` în lista `x`, dacă aceasta este o subsecvență a listei `x`, sau afișează "Datele nu corespund restrictiilor impuse" în caz contrar.

Flaviu at 07:18, 3 May 2023

2023-05-03T07:18:53Z

← Older revision		Revision as of 07:18, 3 May 2023
Line 7:		Line 7:
	== Date de ieșire ==		== Date de ieșire ==
	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou '''va afișa pe ecran numărul p, reprezentând poziția din vectorul x de unde începe secvența y, dacă y este secvență în x, respectiv mesajul NU dacă y nu este secvență în x''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* 1 ≤ m ≤ n ≤ 1000		* 1 ≤ m ≤ n ≤ 1000
	* elementele celor doi vectori vor fi indexate de la 1		* elementele celor doi vectori vor fi indexate de la 1
	* dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții		* dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: 10		: 10
Line 18:		Line 18:
	: 6		: 6
	: 8 5 2 3 10 7		: 8 5 2 3 10 7
			; Ieșire
			: Datele sunt introduse corect.
			: 3

			== Exemplu 2 ==
			; Intrare
			: 1
			: 2 3 4 5 6 7 8 3 1 11 2
			: 4
			: 1 2 3 4 5 6
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	: 3		: 6

	== Rezolvare ==		== Rezolvare ==

Flaviu at 20:24, 28 April 2023

2023-04-28T20:24:23Z

← Older revision		Revision as of 20:24, 28 April 2023
Line 75:		Line 75:
	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	~~Desigur, cu placere!~~

	În acest cod, funcția `read_input()` citeste valorile de intrare de la utilizator și le returnează într-o tuplă, în ordinea în care au fost citite.		În acest cod, funcția `read_input()` citeste valorile de intrare de la utilizator și le returnează într-o tuplă, în ordinea în care au fost citite.

Flaviu at 17:47, 27 April 2023

2023-04-27T17:47:17Z

← Older revision		Revision as of 17:47, 27 April 2023
Line 6:		Line 6:
	Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y.		Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y.
	== Date de ieșire ==		== Date de ieșire ==
	~~Programul~~ va afișa pe ~~ecran~~ numărul p, reprezentând ~~poziția din vectorul x de unde începe secvența y~~, ~~dacă y este secvență în x, respectiv mesajul NU dacă y~~ nu ~~este secvență în x~~.		Dacă datele sunt introduse corect, pe ecran se va afișa:
			'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* 1 ≤ m ≤ n ≤ 1000		* 1 ≤ m ≤ n ≤ 1000
Line 18:		Line 19:
	: 8 5 2 3 10 7		: 8 5 2 3 10 7
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
	: 3		: 3

Line 25:		Line 27:
	# 0519 - Secventa1		# 0519 - Secventa1

	def ~~read_input~~():		def validate_input(n, x, m, y):
	n = ~~int(input()~~)		if not (1 <= n <= 100000 and 1 <= m <= 100000):
	~~x = list(map(int, input~~().~~split())~~)		print("Datele nu corespund restricțiilor impuse.")
	m = ~~int(input~~())		return False
	~~y = list~~(~~map(int, input()~~.~~split())~~)		if not all(1 <= xi <= 1000000 for xi in x) or not all(1 <= yi <= 1000000 for yi in y):
	return ~~n, x, m, y~~		print("Datele nu corespund restricțiilor impuse.")
			return False
			return True

	def is_subsequence(n, x, m, y):		def is_subsequence(n, x, m, y):
Line 38:		Line 41:
	return i + 1		return i + 1
	return -1		return -1

			def read_input():
			try:
			n = int(input("Introduceti numarul de elemente al vectorului x: "))
			x = list(map(int, input("Introduceti elementele vectorului x, separate prin spatiu: ").split()))
			m = int(input("Introduceti numarul de elemente al vectorului y: "))
			y = list(map(int, input("Introduceti elementele vectorului y, separate prin spatiu: ").split()))
			if not validate_input(n, x, m, y):
			print("Datele nu corespund restricțiilor impuse.")
			return None, None, None, None
			print("Datele sunt introduse corect.")
			return n, x, m, y
			except ValueError:
			print("Datele introduse trebuie sa fie numere intregi.")
			return None, None, None, None


	def validate_output(result):		def validate_output(result):
	~~print(result)~~ if result != -1 else print("NU")		if result != -1:
			print(result)
			else:
			print("NU")


	if __name__ == "__main__":		if __name__ == "__main__":
	n, x, m, y = read_input()		n, x, m, y = read_input()
	result = is_subsequence(n, x, m, y)		if n is not None and x is not None and m is not None and y is not None:
	validate_output(result)		result = is_subsequence(n, x, m, y)
			validate_output(result)



Line 53:		Line 76:
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	~~Funcția read_input citește datele de intrare de la tastatură și returnează valorile citite sub formă de tuple.~~		Desigur, cu placere!

	~~Funcția is_subsequence primește cele patru variabile și parcurge vectorul x cu o fereastră de lungime m. Dacă fereastra curentă este identică cu vectorul y~~, ~~atunci întoarce poziția de început a secvenței~~ (~~i + 1~~)~~. Dacă nu găsește nicio secvență~~, ~~întoarce -1~~.		În acest cod, funcția `read_input()` citeste valorile de intrare de la utilizator și le returnează într-o tuplă, în ordinea în care au fost citite.

	Funcția ~~validate_output~~ primește ~~rezultatul întors de is_subsequence~~ și ~~afișează poziția găsită~~ sau ~~mesajul "NU"~~ în caz contrar.		Funcția `is_subsequence(n, x, m, y)` primește 4 argumente, primele două fiind lungimea și elementele listei `x`, iar ultimele două fiind lungimea și elementele listei `y`. Funcția verifică dacă lista `y` este o subsecvență a listei `x` și returnează indexul primului element al primei apariții a listei `y` în lista `x` dacă da, sau `-1` în caz contrar.

	~~În blocul if __name__ ==~~ "~~__main__~~"~~:, apelăm funcțiile~~ în ~~ordinea potrivită pentru a rezolva problema~~.		Funcția `validate_output(result)` primește rezultatul obținut de la `is_subsequence()` și îl afișează în funcție de cerințele problemei, adică afișează indexul primului element al primei apariții a listei `y` în lista `x`, dacă aceasta este o subsecvență a listei `x`, sau afișează "NU" în caz contrar.

Flaviu at 19:48, 17 April 2023

2023-04-17T19:48:09Z

← Older revision		Revision as of 19:48, 17 April 2023
Line 25:		Line 25:
	# 0519 - Secventa1		# 0519 - Secventa1

	n = int(input())		def read_input():
	x = list(map(int, input().split()))		n = int(input())
			x = list(map(int, input().split()))
			m = int(input())
			y = list(map(int, input().split()))
			return n, x, m, y

	~~m = int(input())~~
	~~y = list(map(int, input().split()))~~

	for i in range(n - m + 1):		def is_subsequence(n, x, m, y):
	if x[i:i+m] == y:		for i in range(n - m + 1):
	~~print(~~i+1)		if x[i:i + m] == y:
	~~break~~		return i + 1
	~~else~~:		return -1
	print("NU")

			def validate_output(result):
			print(result) if result != -1 else print("NU")


			if __name__ == "__main__":
			n, x, m, y = read_input()
			result = is_subsequence(n, x, m, y)
			validate_output(result)


	</syntaxhighlight>		</syntaxhighlight>
			== Explicatie Rezolvare ==

			Funcția read_input citește datele de intrare de la tastatură și returnează valorile citite sub formă de tuple.

			Funcția is_subsequence primește cele patru variabile și parcurge vectorul x cu o fereastră de lungime m. Dacă fereastra curentă este identică cu vectorul y, atunci întoarce poziția de început a secvenței (i + 1). Dacă nu găsește nicio secvență, întoarce -1.

			Funcția validate_output primește rezultatul întors de is_subsequence și afișează poziția găsită sau mesajul "NU" în caz contrar.

			În blocul if __name__ == "__main__":, apelăm funcțiile în ordinea potrivită pentru a rezolva problema.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/519/secventa1 0519 - Secventa1] ---- == Cerinţa == Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este secvență în vectorul x. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y. == Date de ieșire == Programul...

2023-03-21T21:12:45Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/519/secventa1 0519 - Secventa1] ---- == Cerinţa == Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este secvență în vectorul x. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y. == Date de ieșire == Programul...

New page

Sursa: [https://www.pbinfo.ro/probleme/519/secventa1 0519 - Secventa1]
----
== Cerinţa ==
Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este secvență în vectorul x.
== Date de intrare ==
Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y.
== Date de ieșire ==
Programul va afișa pe ecran numărul p, reprezentând poziția din vectorul x de unde începe secvența y, dacă y este secvență în x, respectiv mesajul NU dacă y nu este secvență în x.
== Restricţii şi precizări ==
* 1 ≤ m ≤ n ≤ 1000
* elementele celor doi vectori vor fi indexate de la 1
* dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții
== Exemplu ==
; Intrare
: 10
: 8 5 8 5 2 3 10 7 1 6
: 6
: 8 5 2 3 10 7
; Ieșire
: 3

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0519 - Secventa1

n = int(input())
x = list(map(int, input().split()))

m = int(input())
y = list(map(int, input().split()))

for i in range(n - m + 1):
if x[i:i+m] == y:
print(i+1)
break
else:
print("NU")

</syntaxhighlight>