3273 - cmmdcsecv - Revision history

Monica Dragos: /* Date de ieșire */

2023-05-14T22:34:59Z

Date de ieșire

← Older revision		Revision as of 22:34, 14 May 2023
Line 15:		Line 15:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire cmmdcsecv.out va conține:~~
	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 '''~~pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.'', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''' cmmdcsecv.out va conține pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.'', 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 ==
	* 3 ≤ n ≤ 100.000		* 3 ≤ n ≤ 100.000

Monica Dragos at 22:34, 14 May 2023

2023-05-14T22:34:28Z

← Older revision		Revision as of 22:34, 14 May 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/3273/cmmdcsecv 3273 - cmmdcsecv]		Sursa: [https://www.pbinfo.ro/probleme/3273/cmmdcsecv 3273 - cmmdcsecv]
	----		----
	Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1.


			== Cerinţa ==
			Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din
			șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1.

	~~== Cerinţa ==~~
	Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvență este strict mai mare decât 1.		Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvență este strict mai mare decât 1.

Flaviu at 21:48, 14 May 2023

2023-05-14T21:48:42Z

← Older revision		Revision as of 21:48, 14 May 2023
Line 26:		Line 26:
	: 15 28 14 56 42 5		: 15 28 14 56 42 5
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: cmmdcsecv.out		: cmmdcsecv.out
	~~: Datele sunt introduse correct.~~
	: 4		: 4

Line 36:		Line 36:
	: 23 5 7 15 28 14 56 42 5		: 23 5 7 15 28 14 56 42 5
	; Ieșire		; Ieșire
	~~: cmmdcsecv.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 45:		Line 44:
	# 3273 - cmmdcsecv		# 3273 - cmmdcsecv

	~~import math~~		def calculate_gcd(a, b):
			while b:
			a, b = b, a % b
			return a

	~~def read_input():~~
	~~with open("cmmdcsecv.in", "r") as f:~~
	~~n = int(f.readline())~~
	~~arr = list(map(int, f.readline().split()))~~
	~~return n, arr~~

	def ~~cmmdcsecv~~(n, ~~arr~~):		def find_longest_sequence(n, nums):
	~~max_len~~ = 0 ~~# lungimea maxima a secventei~~		max_length = 0
			current_length = 0

	for i in range(n):		for i in range(n):
	~~d = arr[i] # cel mai mare divizor comun~~		for j in range(i, n):
	for j in range(i ~~+ 1~~, n):		valid = True
	d = ~~math.gcd~~(d, ~~arr~~[j])		for k in range(i, j + 1):
	if ~~d > 1~~:		if calculate_gcd(nums[k], nums[k + 1]) == 1:
	~~max_len~~ = ~~max(max_len,~~ j - i + 1)		valid = False
	return ~~max_len~~		break
			if valid:
			current_length = j - i + 1
			max_length = max(max_length, current_length)

			return max_length


			def validate_input(n, nums):
			if n < 3 or n > 100000 or len(nums) != n or any(num < 1 or num > 1000 for num in nums):
			return False
			return True

	~~def validate_output(result):~~
	~~with open("cmmdcsecv.out", "r") as f:~~
	~~expected_result = int(f.readline())~~
	~~assert result == expected_result, f"Error: expected {expected_result}, but got {result}"~~

	if __name__ == "__main__":		if __name__ == "__main__":
	n~~, arr~~ = ~~read_input~~()		with open("cmmdcsecv.in", "r") as file:
	~~result~~ = ~~cmmdcsecv~~(n, ~~arr~~)		n = int(file.readline())
	~~try:~~		nums = list(map(int, file.readline().split()))
	~~validate_output~~(~~result~~)
			if validate_input(n, nums):
	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	~~except AssertionError~~:		result = find_longest_sequence(n, nums)
			with open("cmmdcsecv.out", "w") as file:
			file.write(str(result))
			else:
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	~~print(result)~~



	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Acest cod~~ este ~~o implementare în Python a algoritmului pentru~~ a găsi ~~cea~~ mai ~~lungă secvență a unei liste date de numere~~ în care ~~toate numerele~~ din secvență ~~au un divizor comun~~ mai mare decât 1.		calculate_gcd(a, b): Această funcție primește două numere a și b și calculează cel mai mare divizor comun (CMMD) folosind algoritmul lui Euclid. Returnează rezultatul CMMD.

			find_longest_sequence(n, nums): Această funcție primește un număr n reprezentând lungimea șirului și o listă nums care conține elementele șirului. Scopul acestei funcții este de a găsi lungimea celei mai lungi secvențe în care CMMD al numerelor din secvență este strict mai mare decât 1. Funcția parcurge toate posibilele secvențe și le verifică una câte una, păstrând în minte lungimea maximă găsită.

	~~Mai exact~~, ~~codul citeste~~ datele de intrare ~~din fișierul "cmmdcsecv~~.~~in", care conține pe prima linie numărul de elemente din lista~~ și ~~pe a doua linie lista~~ în sine. Apoi, calculează lungimea maximă a unei secvențe cu numere care au un divizor comun mai mare decât 1. În final, codul verifică dacă rezultatul obținut este corect prin comparație cu rezultatul așteptat din fișierul "cmmdcsecv.out".		validate_input(n, nums): Această funcție primește un număr n reprezentând lungimea șirului și o listă nums cu elementele șirului. Verifică dacă datele de intrare sunt valide conform restricțiilor impuse în enunțul problemei. Returnează True dacă datele sunt valide și False în caz contrar.

	În ~~această versiune modificată a codului,~~ se verifică dacă ~~rezultatul obținut este corect și se afișează un mesaj corespunzător în funcție de acesta~~. Dacă ~~rezultatul este corect~~, se afișează "Datele sunt introduse corect." și se ~~afișează lungimea secvenței~~. Dacă ~~rezultatul~~ nu ~~este corect~~, se afișează "Datele nu corespund restricțiilor impuse." ~~și se afișează lungimea secvenței.~~		Blocul if __name__ == "__main__": În acest bloc se efectuează citirea datelor de intrare din fișierul "cmmdcsecv.in". Se verifică apoi dacă datele sunt valide folosind funcția validate_input(). Dacă datele sunt valide, se afișează mesajul "Datele sunt introduse corect." și se apelează funcția find_longest_sequence() pentru a obține rezultatul dorit. Rezultatul este apoi scris în fișierul "cmmdcsecv.out". Dacă datele nu sunt valide, se afișează mesajul "Datele nu corespund restricțiilor impuse."

Flaviu at 08:06, 3 May 2023

2023-05-03T08:06:42Z

← Older revision		Revision as of 08:06, 3 May 2023
Line 16:		Line 16:
	Fișierul de ieșire cmmdcsecv.out va conține:		Fișierul de ieșire cmmdcsecv.out va conține:
	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 '''pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.'', 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 ==
	* 3 ≤ n ≤ 100.000		* 3 ≤ n ≤ 100.000
	* 1 ≤ ai ≤ 1000, pentru orice 1 ≤ i ≤ n		* 1 ≤ ai ≤ 1000, pentru orice 1 ≤ i ≤ n
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: cmmdcsecv.in
	: 6		: 6
	: 15 28 14 56 42 5		: 15 28 14 56 42 5
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: cmmdcsecv.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 4		: 4

			== Exemplu 1 ==
			; Intrare
			: cmmdcsecv.in
			: -6
			: 23 5 7 15 28 14 56 42 5
			; Ieșire
			: cmmdcsecv.out
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:53, 28 April 2023

2023-04-28T14:53:08Z

← Older revision		Revision as of 14:53, 28 April 2023
Line 14:		Line 14:

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire cmmdcsecv.out va conține un ~~singur număr natural~~ reprezentând ~~lungimea maximă a unei secvențe care are cel mai mare divizor comun strict mai mare decât 1~~.		Fișierul de ieșire cmmdcsecv.out va conține:
			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 ==
	* 3 ≤ n ≤ 100.000		* 3 ≤ n ≤ 100.000
Line 24:		Line 25:
	: 15 28 14 56 42 5		: 15 28 14 56 42 5
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 4		: 4

Line 57:		Line 60:
	n, arr = read_input()		n, arr = read_input()
	result = cmmdcsecv(n, arr)		result = cmmdcsecv(n, arr)
	validate_output(result)		try:
			validate_output(result)
			print("Datele sunt introduse corect.")
			except AssertionError:
			print("Datele nu corespund restricțiilor impuse.")
	print(result)		print(result)



	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Pentru~~ a ~~rezolva această problemă, putem folosi o metodă similară cu algoritmul de căutare~~ a ~~celei~~ mai ~~lungi subsecvențe crescătoare (LIS). Vom parcurge șirul și vom calcula cel~~ mai mare ~~divizor comun (CMMD) între fiecare element~~ și ~~toate elementele următoare~~. ~~Dacă cel mai mare~~ divizor comun ~~este strict~~ mai mare decât 1, ~~atunci avem o secvență validă~~ și ~~vom actualiza~~ lungimea ~~maximă a~~ secvenței.		Acest cod este o implementare în Python a algoritmului pentru a găsi cea mai lungă secvență a unei liste date de numere în care toate numerele din secvență au un divizor comun mai mare decât 1.

			Mai exact, codul citeste datele de intrare din fișierul "cmmdcsecv.in", care conține pe prima linie numărul de elemente din lista și pe a doua linie lista în sine. Apoi, calculează lungimea maximă a unei secvențe cu numere care au un divizor comun mai mare decât 1. În final, codul verifică dacă rezultatul obținut este corect prin comparație cu rezultatul așteptat din fișierul "cmmdcsecv.out".

			În această versiune modificată a codului, se verifică dacă rezultatul obținut este corect și se afișează un mesaj corespunzător în funcție de acesta. Dacă rezultatul este corect, se afișează "Datele sunt introduse corect." și se afișează lungimea secvenței. Dacă rezultatul nu este corect, se afișează "Datele nu corespund restricțiilor impuse." și se afișează lungimea secvenței.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3273/cmmdcsecv 3273 - cmmdcsecv] ---- Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1. == Cerinţa == Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvenț...

2023-04-18T07:09:11Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3273/cmmdcsecv 3273 - cmmdcsecv] ---- Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1. == Cerinţa == Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvenț...

New page

Sursa: [https://www.pbinfo.ro/probleme/3273/cmmdcsecv 3273 - cmmdcsecv]
----
Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1.

== Cerinţa ==
Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvență este strict mai mare decât 1.

== Date de intrare ==
Fișierul de intrare cmmdcsecv.in conține pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.

== Date de ieșire ==
Fișierul de ieșire cmmdcsecv.out va conține un singur număr natural reprezentând lungimea maximă a unei secvențe care are cel mai mare divizor comun strict mai mare decât 1.

== Restricţii şi precizări ==
* 3 ≤ n ≤ 100.000
* 1 ≤ ai ≤ 1000, pentru orice 1 ≤ i ≤ n
== Exemplu ==
; Intrare
: 6
: 15 28 14 56 42 5
; Ieșire
: 4

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3273 - cmmdcsecv

import math

def read_input():
with open("cmmdcsecv.in", "r") as f:
n = int(f.readline())
arr = list(map(int, f.readline().split()))
return n, arr

def cmmdcsecv(n, arr):
max_len = 0 # lungimea maxima a secventei
for i in range(n):
d = arr[i] # cel mai mare divizor comun
for j in range(i + 1, n):
d = math.gcd(d, arr[j])
if d > 1:
max_len = max(max_len, j - i + 1)
return max_len

def validate_output(result):
with open("cmmdcsecv.out", "r") as f:
expected_result = int(f.readline())
assert result == expected_result, f"Error: expected {expected_result}, but got {result}"

if __name__ == "__main__":
n, arr = read_input()
result = cmmdcsecv(n, arr)
validate_output(result)
print(result)

</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru a rezolva această problemă, putem folosi o metodă similară cu algoritmul de căutare a celei mai lungi subsecvențe crescătoare (LIS). Vom parcurge șirul și vom calcula cel mai mare divizor comun (CMMD) între fiecare element și toate elementele următoare. Dacă cel mai mare divizor comun este strict mai mare decât 1, atunci avem o secvență validă și vom actualiza lungimea maximă a secvenței.