0522 - kSecventa1 - Revision history

Flaviu at 20:02, 14 May 2023

2023-05-14T20:02:49Z

← Older revision		Revision as of 20:02, 14 May 2023
Line 60:		Line 60:
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	Funcția ~~validate_input(~~n, k, ~~arr) verifică dacă intrarea este validă și întoarce~~ un ~~rezultat boolean care indică dacă intrarea este validă sau nu~~. ~~Mai exact~~, ~~verifică dacă~~ k ~~este mai mic decât n, dacă n este divizibil~~ cu k, ~~iar dacă toate elementele din vectorul arr sunt mai mici sau egale cu 1000~~.		Funcția gaseste_secvente_identice primește trei argumente: n - numărul de elemente din șirul dat, k - lungimea secvenței identice și v - șirul de numere. Dacă n nu este un multiplu de k, funcția returnează un mesaj de eroare. Apoi, cu ajutorul două loop-uri, caută toate secvențele de lungime k și le compară cu toate secvențele de lungime k din dreapta sa. Dacă găsește o secvență identică, returnează pozițiile unde a fost găsită. Dacă nu găsește nicio secvență identică, funcția returnează un mesaj corespunzător.

	Funcția ~~find_identical_sequences(n, k, arr) caută~~ și ~~afișează pe ecran două secvențe identice de lungime k din vectorul arr,~~ dacă ~~există. Pentru a face acest lucru, împarte vectorul în sub-secvențe~~ de ~~lungime k, creând o secvență din fiecare sub-secvență și verificând dacă secvența respectivă există deja într-un dicționar~~. Dacă ~~secvența există deja în dicționar~~, ~~înseamnă că am găsit două secvențe identice și le afișăm pozițiile~~. ~~Dacă ajungem la sfârșitul vectorului și nu găsim nicio pereche de secvențe identice~~, ~~afișăm mesajul "NU"~~.		Funcția valideaza_date_intrare primește aceleași argumente ca și gaseste_secvente_identice și verifică dacă datele de intrare corespund cerințelor problemei. Dacă nu respectă aceste condiții, funcția returnează False. Altfel, returnează True.

	~~Funcția principală~~ if __name__ == "__main__" citește ~~datele~~ de ~~intrare~~ și, dacă ~~acestea~~ sunt ~~valide~~, afișează mesajul "Datele sunt introduse corect." și apelează funcția ~~find_identical_sequences(n, k, arr) pentru a căuta secvențele identice~~. Dacă ~~datele de intrare~~ nu ~~sunt valide~~, se afișează mesajul "Datele nu corespund restricțiilor impuse."		În if __name__ == "__main__": se citește de la tastatură valorile lui n, k și șirul v. Apoi, se verifică dacă datele sunt introduse corect cu ajutorul funcției valideaza_date_intrare. Dacă da, se afișează mesajul "Datele sunt introduse corect." și se apelează funcția gaseste_secvente_identice. Dacă nu, se afișează mesajul "Datele nu corespund restricțiilor impuse.".

Flaviu at 20:00, 14 May 2023

2023-05-14T20:00:46Z

← Older revision		Revision as of 20:00, 14 May 2023
Line 25:		Line 25:
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	~~: 3 5~~

	== Rezolvare ==		== Rezolvare ==
Line 31:		Line 31:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 0522 - kSecventa1		# 0522 - kSecventa1
	def ~~kSecventa~~(n, k, v):		def gaseste_secvente_identice(n, k, v):
	if n % k != 0:		if n % k != 0:
	~~print(~~"Datele nu corespund restricțiilor impuse.")		return "Datele nu corespund restricțiilor impuse."
	~~return~~
			for i in range(0, n-k+1):
	~~# Impartim lista in k bucati cat mai egale~~		if v[i:i+k] in [v[j:j+k] for j in range(i+1, n-k+1)]:
	~~chunk_size = n // k~~		return f"{i+1} {v.index(v[i:i+k], i+1)+1}"
	~~extra = n % k~~
	~~chunks = []~~		return "Nu exista secvente identice."
	~~start = 0~~
	for i in range(k):
	~~end = start + chunk_size~~
	if ~~extra > 0~~:
	~~end~~ +~~= 1~~
	~~extra -= 1~~
	~~chunks.append(~~v[~~start~~:~~end~~])
	~~start = end~~

	~~# Verificam daca exista doua secvente identice~~
	~~for i in range(k):~~
	for j in range(i+1, k):
	~~if chunks~~[i~~] == chunks[j]~~:
	~~print("Datele sunt introduse corect.")~~
	~~print(~~ichunk_size+1, ~~jchunk_size~~+1)
	~~return~~

	~~print(~~"~~Datele sunt introduse corect~~.")
	~~print("NU")~~


			def valideaza_date_intrare(n, k, v):
			if not (1 <= k < n <= 1000 and n % k == 0):
			return False
			if any(x >= 1000 for x in v):
			return False
			return True
	if __name__ == "__main__":		if __name__ == "__main__":
	n, k = map(int, input().split())		n, k = map(int, input().split())
	~~if not (isinstance(n, int) and isinstance(k, int) and n > 1 and k > 1):~~
	~~print("Datele nu corespund restricțiilor impuse.")~~
	~~exit()~~

	~~if n % k != 0:~~
	~~print("Datele nu corespund restricțiilor impuse.")~~
	~~exit()~~

	v = list(map(int, input().split()))		v = list(map(int, input().split()))
	if ~~not~~ (~~len~~(v) ~~== n and all~~(~~isinstance~~(x, ~~int) and x > 0 and x < 1000 for x in~~ v)):
			if valideaza_date_intrare(n, k, v):
			print("Datele sunt introduse corect.")
			print(gaseste_secvente_identice(n, k, v))
			else:
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	~~exit()~~

	~~kSecventa(n, k, v)~~

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

	Funcția ~~kSecventa primește ca argumente lungimea vectorului~~ n, ~~lungimea secvențelor~~ k și ~~vectorul v. În cazul în~~ care ~~lungimea vectorului~~ nu ~~se împarte~~ exact ~~la lungimea secvențelor~~, ~~se afișează mesajul "Datele nu corespund restricțiilor impuse~~." și ~~se încheie execuția funcției~~. ~~Altfel~~, se împarte vectorul în k ~~bucăți cât mai egale~~ și ~~se verifică~~ dacă există două secvențe identice. Dacă ~~se găsește o astfel de secvență, se afișează mesajul "Datele sunt introduse corect."~~ și ~~pozițiile~~ de ~~început ale celor două~~ secvențe~~. În caz contrar~~, ~~se afișează~~ mesajul ~~"Datele sunt introduse corect." și~~ "NU".		Funcția validate_input(n, k, arr) verifică dacă intrarea este validă și întoarce un rezultat boolean care indică dacă intrarea este validă sau nu. Mai exact, verifică dacă k este mai mic decât n, dacă n este divizibil cu k, iar dacă toate elementele din vectorul arr sunt mai mici sau egale cu 1000.
	~~In funcția~~ if __name__ == "__main__"~~:, valorile~~ de intrare sunt ~~citite~~ și ~~apoi apelăm~~ funcția ~~kSecventa~~(n, k, v) ~~cu valorile citite ca argumente~~. ~~În plus, validarea datelor~~ de intrare ~~este realizată în același mod ca în codul anterior. Deci,~~ nu ~~trebuie să rescriem codul pentru funcția kSecventa(n~~, ~~k, v) în funcția if __name__ ==~~ "~~__main__~~"~~:..~~
			Funcția find_identical_sequences(n, k, arr) caută și afișează pe ecran două secvențe identice de lungime k din vectorul arr, dacă există. Pentru a face acest lucru, împarte vectorul în sub-secvențe de lungime k, creând o secvență din fiecare sub-secvență și verificând dacă secvența respectivă există deja într-un dicționar. Dacă secvența există deja în dicționar, înseamnă că am găsit două secvențe identice și le afișăm pozițiile. Dacă ajungem la sfârșitul vectorului și nu găsim nicio pereche de secvențe identice, afișăm mesajul "NU".

			Funcția principală if __name__ == "__main__" citește datele de intrare și, dacă acestea sunt valide, afișează mesajul "Datele sunt introduse corect." și apelează funcția find_identical_sequences(n, k, arr) pentru a căuta secvențele identice. Dacă datele de intrare nu sunt valide, se afișează mesajul "Datele nu corespund restricțiilor impuse."

Flaviu at 21:19, 13 May 2023

2023-05-13T21:19:26Z

← Older revision		Revision as of 21:19, 13 May 2023
Line 31:		Line 31:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 0522 - kSecventa1		# 0522 - kSecventa1
	def ~~citire_date~~():		def kSecventa(n, k, v):
	n = ~~int(input~~())		if n % k != 0:
	k = ~~int~~(~~input~~())		print("Datele nu corespund restricțiilor impuse.")
	~~v = list~~(~~map~~(~~int~~, ~~input~~()~~.split~~()))		return
	return ~~n, k, v~~
			# Impartim lista in k bucati cat mai egale
			chunk_size = n // k
			extra = n % k
			chunks = []
			start = 0
			for i in range(k):
			end = start + chunk_size
			if extra > 0:
			end += 1
			extra -= 1
			chunks.append(v[start:end])
			start = end

			# Verificam daca exista doua secvente identice
			for i in range(k):
			for j in range(i+1, k):
			if chunks[i] == chunks[j]:
			print("Datele sunt introduse corect.")
			print(ichunk_size+1, jchunk_size+1)
			return

	~~def gaseste_secvente_identice~~(~~n, k, v~~):		print("Datele sunt introduse corect.")
	~~secvente = {}~~		print("NU")
	~~for i in range(n - k + 1):~~
	~~secventa = tuple~~(~~v[i:i+k])~~
	~~if secventa in secvente:~~
	~~return secvente[secventa], i~~
	~~else:~~
	~~secvente[secventa] = i~~
	~~return~~ "NU"

	~~def valideaza(n, k, v):~~
	~~if n <= k:~~
	~~return "NU"~~
	~~return " ".join(str(i) for i in gaseste_secvente_identice(n, k, v))~~

	if __name__ == "__main__":		if __name__ == "__main__":
	n, k, ~~v = citire_date~~()		n, k = map(int, input().split())
	~~rezultat = valideaza~~(n, k, v)		if not (isinstance(n, int) and isinstance(k, int) and n > 1 and k > 1):
	~~if rezultat != "NU"~~:		print("Datele nu corespund restricțiilor impuse.")
	print("Datele ~~sunt introduse corect~~.")		exit()
	~~else~~:
			if n % k != 0:
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	~~print~~(~~rezultat~~)		exit()

			v = list(map(int, input().split()))
			if not (len(v) == n and all(isinstance(x, int) and x > 0 and x < 1000 for x in v)):
			print("Datele nu corespund restricțiilor impuse.")
			exit()

			kSecventa(n, k, v)

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Funcția citire_date() primește input-ul și returnează cele trei variabile citite.~~
	Funcția ~~gaseste_secvente_identice(n, k, v)~~ primește ~~dimensiunea~~ vectorului n, lungimea secvențelor k și vectorul v, ~~și returnează o pereche de numere care reprezintă pozițiile de început ale celor două secvențe identice sau un string~~ "NU" ~~în caz contrar~~. ~~Pentru a găsi secvențele identice~~, se ~~parcurg toate secvențele de lungime~~ k ~~din vector, iar pentru fiecare se construiește un tuplu~~ și se verifică dacă ~~apare într-un dicționar de~~ secvențe ~~întâlnite anterior~~. Dacă ~~apare~~, se ~~returnează~~ pozițiile celor două secvențe ~~identice~~, ~~altfel~~ se ~~adaugă tuplul în dicționar~~.		Funcția kSecventa primește ca argumente lungimea vectorului n, lungimea secvențelor k și vectorul v. În cazul în care lungimea vectorului nu se împarte exact la lungimea secvențelor, se afișează mesajul "Datele nu corespund restricțiilor impuse." și se încheie execuția funcției. Altfel, se împarte vectorul în k bucăți cât mai egale și se verifică dacă există două secvențe identice. Dacă se găsește o astfel de secvență, se afișează mesajul "Datele sunt introduse corect." și pozițiile de început ale celor două secvențe. În caz contrar, se afișează mesajul "Datele sunt introduse corect." și "NU".
	~~Funcția valideaza~~(n, k, v) ~~primește aceleași trei variabile și returnează "NU" dacă n<=k sau rezultatul funcției gaseste_secvente_identice~~(n, k, v) ~~altfel. Dacă există două secvențe identice, se întorc pozițiile lor, altfel se întoarce string-ul "NU".~~		In funcția if __name__ == "__main__":, valorile de intrare sunt citite și apoi apelăm funcția kSecventa(n, k, v) cu valorile citite ca argumente. În plus, validarea datelor de intrare este realizată în același mod ca în codul anterior. Deci, nu trebuie să rescriem codul pentru funcția kSecventa(n, k, v) în funcția if __name__ == "__main__":..
	~~Blocul~~ if __name__ == "__main__": ~~este necesar pentru a permite rularea funcțiilor din consolă~~. ~~În acest bloc se citesc datele de intrare, se validează și se afișează rezultatul~~.

Flaviu at 07:23, 3 May 2023

2023-05-03T07:23:05Z

← Older revision		Revision as of 07:23, 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 '''Programul va afișa pe ecran numerele i j, i < j reprezentând pozițiile de început a două secvențe de lungime k identice, dacă există două astfel de secvențe''', 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 ≤ k < n ≤ 1000, k este divizor al lui n		* 1 ≤ k < n ≤ 1000, k este divizor al lui n
	* cele n numere citite vor fi mai mici decât 1000		* cele n numere citite vor fi mai mici decât 1000
	== Exemplu ==		== Exemplu 1 ==
			; Intrare
			: 12 5
			: 2 3 1 1 4 3 1 1 4 3 8 8
			; Ieșire
			: Datele sunt introduse corect.
			: 2 6

			== Exemplu 2 ==
	; Intrare		; Intrare
	: 12 5		: 12 5
Line 17:		Line 25:
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	: ~~2 6~~		: 3 5

	== Rezolvare ==		== Rezolvare ==

Flaviu at 18:08, 27 April 2023

2023-04-27T18:08:22Z

← Older revision		Revision as of 18:08, 27 April 2023
Line 6:		Line 6:
	Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.		Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.
	== Date de ieșire ==		== Date de ieșire ==
	~~Programul~~ va afișa pe ~~ecran numerele i j~~, ~~i < j~~ reprezentând ~~pozițiile de început a două secvențe de lungime k identice~~, ~~dacă există două astfel de secvențe, sau mesajul NU, dacă~~ nu ~~există două astfel de secvențe~~.		Dacă datele sunt introduse corect, pe ecran se va afișa:
	~~Dacă există mai multe perechi de secvențe identice se vor considera cele cu numerele de ordine i j minime~~.		'''"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 ≤ k < n ≤ 1000, k este divizor al lui n		* 1 ≤ k < n ≤ 1000, k este divizor al lui n
Line 16:		Line 16:
	: 2 3 1 1 4 3 1 1 4 3 8 8		: 2 3 1 1 4 3 1 1 4 3 8 8
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
	: 2 6		: 2 6

Line 22:		Line 23:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 0522 - kSecventa1		# 0522 - kSecventa1

	def citire_date():		def citire_date():
	n = int(input())		n = int(input())
Line 46:		Line 46:
	if __name__ == "__main__":		if __name__ == "__main__":
	n, k, v = citire_date()		n, k, v = citire_date()
	~~print(~~valideaza(n, k, v))		rezultat = valideaza(n, k, v)
			if rezultat != "NU":
			print("Datele sunt introduse corect.")
			else:
			print("Datele nu corespund restricțiilor impuse.")
			print(rezultat)


	</syntaxhighlight>		</syntaxhighlight>

Flaviu at 19:53, 17 April 2023

2023-04-17T19:53:16Z

← Older revision		Revision as of 19:53, 17 April 2023
Line 23:		Line 23:
	# 0522 - kSecventa1		# 0522 - kSecventa1

	n~~, k~~ = ~~map~~(~~int,~~ input()~~.split~~())		def citire_date():
	v = list(map(int, input().split()))		n = int(input())
			k = int(input())
			v = list(map(int, input().split()))
			return n, k, v

	~~found~~ = ~~False~~		def gaseste_secvente_identice(n, k, v):
			secvente = {}
			for i in range(n - k + 1):
			secventa = tuple(v[i:i+k])
			if secventa in secvente:
			return secvente[secventa], i
			else:
			secvente[secventa] = i
			return "NU"

	~~for i in range~~(n - k ~~+ 1~~):		def valideaza(n, k, v):
	~~for j in range(i + 1,~~ n - k ~~+ 1)~~:		if n <= k:
	~~if v[~~i:i+k~~] ==~~ v~~[j:j+k]:~~		return "NU"
	~~print(i+1, j+1~~)		return " ".join(str(i) for i in gaseste_secvente_identice(n, k, v))
	~~found = True~~
	~~break~~
	~~if found:~~
	~~break~~

	~~if not found:~~
	~~print("NU"~~)

			if __name__ == "__main__":
			n, k, v = citire_date()
			print(valideaza(n, k, v))

	</syntaxhighlight>		</syntaxhighlight>
			== Explicatie Rezolvare ==
			Funcția citire_date() primește input-ul și returnează cele trei variabile citite.
			Funcția gaseste_secvente_identice(n, k, v) primește dimensiunea vectorului n, lungimea secvențelor k și vectorul v, și returnează o pereche de numere care reprezintă pozițiile de început ale celor două secvențe identice sau un string "NU" în caz contrar. Pentru a găsi secvențele identice, se parcurg toate secvențele de lungime k din vector, iar pentru fiecare se construiește un tuplu și se verifică dacă apare într-un dicționar de secvențe întâlnite anterior. Dacă apare, se returnează pozițiile celor două secvențe identice, altfel se adaugă tuplul în dicționar.
			Funcția valideaza(n, k, v) primește aceleași trei variabile și returnează "NU" dacă n<=k sau rezultatul funcției gaseste_secvente_identice(n, k, v) altfel. Dacă există două secvențe identice, se întorc pozițiile lor, altfel se întoarce string-ul "NU".
			Blocul if __name__ == "__main__": este necesar pentru a permite rularea funcțiilor din consolă. În acest bloc se citesc datele de intrare, se validează și se afișează rezultatul.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/522/ksecventa1 0522 - kSecventa1] ---- == Cerinţa == Se dă un vector cu n elemente, numere naturale, și un număr k. Să se stabilească dacă în vector există două secvențe de lungime k identice. == Date de intrare == Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului. == Date de ieșire == Programul va afișa pe ecran numerele i j, i < j reprezentând pozițiile...

2023-03-21T21:23:26Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/522/ksecventa1 0522 - kSecventa1] ---- == Cerinţa == Se dă un vector cu n elemente, numere naturale, și un număr k. Să se stabilească dacă în vector există două secvențe de lungime k identice. == Date de intrare == Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului. == Date de ieșire == Programul va afișa pe ecran numerele i j, i < j reprezentând pozițiile...

New page

Sursa: [https://www.pbinfo.ro/probleme/522/ksecventa1 0522 - kSecventa1]
----
== Cerinţa ==
Se dă un vector cu n elemente, numere naturale, și un număr k. Să se stabilească dacă în vector există două secvențe de lungime k identice.
== Date de intrare ==
Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.
== Date de ieșire ==
Programul va afișa pe ecran numerele i j, i < j reprezentând pozițiile de început a două secvențe de lungime k identice, dacă există două astfel de secvențe, sau mesajul NU, dacă nu există două astfel de secvențe.
Dacă există mai multe perechi de secvențe identice se vor considera cele cu numerele de ordine i j minime.
== Restricţii şi precizări ==
* 1 ≤ k < n ≤ 1000, k este divizor al lui n
* cele n numere citite vor fi mai mici decât 1000
== Exemplu ==
; Intrare
: 12 5
: 2 3 1 1 4 3 1 1 4 3 8 8
; Ieșire
: 2 6

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0522 - kSecventa1

n, k = map(int, input().split())
v = list(map(int, input().split()))

found = False

for i in range(n - k + 1):
for j in range(i + 1, n - k + 1):
if v[i:i+k] == v[j:j+k]:
print(i+1, j+1)
found = True
break
if found:
break

if not found:
print("NU")

</syntaxhighlight>