1673 - Cmmdc 1 - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-27T13:15:23Z

Rezolvare

← Older revision		Revision as of 13:15, 27 December 2023
Line 42:		Line 42:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	~~from math import gcd~~		def verifica_restrictii(n, k, a):
			if not (1 <= n <= 1000000):
			return False
			if not (2 <= k <= 100000 and k <= n):
			return False
			if not all(1 <= elem <= 1000000 for elem in a):
			return False
			return True

	def cmmdc(a, b):		def cmmdc(a, b):
Line 49:		Line 56:
	return a		return a

	def ~~grup_cmmdc_maxim~~(n, k, numere):		def gaseste_grup_max_cmmdc(n, k, numere):
	~~grup_maxim~~ = []		numere.sort(reverse=True)
	~~cmmdc_maxim~~ = 0		max_cmmdc = 0
			grup_max_cmmdc = []

	for i in range(~~n -~~ k ~~+ 1~~):		for i in range(k):
	grup = numere[i:i+k]		grup = numere[:i] + numere[i + 1:k]
	~~cmmdc_grup~~ = grup[0]		gcd = grup[0]
	for ~~numar~~ in grup[1:]:		for elem in grup[1:]:
	~~cmmdc_grup~~ = cmmdc(~~cmmdc_grup~~, ~~numar~~)		gcd = cmmdc(gcd, elem)
			if gcd > max_cmmdc or (gcd == max_cmmdc and sum(grup) > sum(grup_max_cmmdc)):
	if ~~cmmdc_grup~~ > ~~cmmdc_maxim~~:		max_cmmdc = gcd
	~~cmmdc_maxim~~ = ~~cmmdc_grup~~		grup_max_cmmdc = grup
	~~grup_maxim~~ = grup

	return ~~cmmdc_maxim~~, ~~grup_maxim~~		return max_cmmdc, grup_max_cmmdc

	# Citire ~~date~~ de intrare		# Citire din fișierul de intrare
	with open(~~"cmmdc1~~.txt", "r") as file:		with open('cmmdc1in.txt', 'r') as file:
	n, k = map(int, file.readline().split())		n, k = map(int, file.readline().split())
	numere = list(map(int, file.readline().split()))		numere = list(map(int, file.readline().split()))

	# ~~Rezolvare problema~~		# Verificare restricții
	~~rezultat_cmmdc~~, ~~rezultat_grup~~ = ~~grup_cmmdc_maxim~~(n, k, numere)		if verifica_restrictii(n, k, numere):
			# Găsire grup cu cel mai mare divizor comun
			rezultat = gaseste_grup_max_cmmdc(n, k, numere)

	# Scriere ~~rezultat~~ în fișierul de ieșire		# Scriere în fișierul de ieșire
	with open(~~"cmmdc1~~.txt", "w") as file_out:		with open('cmmdc1out.txt', 'w') as file_out:
	file_out.write(~~str(rezultat_cmmdc) +~~ "\n")		file_out.write(f"{rezultat[0]}\n")
	file_out.write(~~" "~~.join(map(str, ~~sorted(rezultat_grup, reverse=True~~))))		file_out.write(' '.join(map(str, rezultat[1])))
			else:
			print("Date de intrare nevalide.")

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa at 13:13, 27 December 2023

2023-12-27T13:13:17Z

← Older revision		Revision as of 13:13, 27 December 2023
Line 1:		Line 1:
	== Enunt ==		== Enunt ==

	Fie un șir de numere naturale nenule a[1], a[2], …, a[n] și un număr natural k.		Fie un șir de numere naturale nenule '''a[1], a[2], …, a[n]''' și un număr natural '''k'''.

	== Cerinta ==		== Cerinta ==

	Să se determine un grup de k numere din șir care au proprietatea că cel mai mare divizor comun al lor este maxim. Dacă există mai multe astfel de grupuri, se cere acel grup pentru care suma elementelor este maximă.		Să se determine un grup de '''k''' numere din șir care au proprietatea că cel mai mare divizor comun al lor este maxim. Dacă există mai multe astfel de grupuri, se cere acel grup pentru care suma elementelor este maximă.

	== Date de intrare ==		== Date de intrare ==

	Fișierul de intrare ~~cmmdc1~~.txt conține pe prima numerele naturale n k separate prin spațiu. Pe linia a doua se găsesc numerele naturale a[1], a[2], …, a[n] separate prin câte un spațiu.		Fișierul de intrare '''cmmdc1in.txt''' conține pe prima numerele naturale '''n k''' separate prin spațiu. Pe linia a doua se găsesc numerele naturale '''a[1], a[2], …, a[n]''' separate prin câte un spațiu.

	== Date de iesire ==		== Date de iesire ==

	Fișierul de ieșire ~~cmmdc1~~.txt va conține pe prima linie un număr natural reprezentând cel mai mare divizor comun a exact k numere din șir, maxim posibil. Pe linia a doua, separate prin câte un spațiu și ordonate descrescător, se află cele k numere din șir care dau cel mai mare divizor comun maxim.		Fișierul de ieșire '''cmmdc1out.txt''' va conține pe prima linie un număr natural reprezentând cel mai mare divizor comun a exact '''k''' numere din șir, maxim posibil. Pe linia a doua, separate prin câte un spațiu și ordonate descrescător, se află cele k numere din șir care dau cel mai mare divizor comun maxim.

	== Restrictii si precizari ==		== Restrictii si precizari ==

	*1 ≤ n ≤ 1.000.000		*'''1 &les; n &les; 1.000.000'''
	*2 ≤ k ≤ 100.000		*'''2 &les; k &les; 100.000'''
	*k ≤ n		*k &les; n
	*1 ≤ a[i] ≤ 1.000.000, i = 1..n		*1 &les; a[i] &les; 1.000.000, i = 1..n
	*Valorile din șir se pot repeta.		*Valorile din șir se pot repeta.

	== Exemplul 1 ==		== Exemplul 1 ==
	;~~Intrare~~		;cmmdc1in.txt
	:6 3		:6 3
	:6 9 8 10 15 3		:6 9 8 10 15 3
	;~~Iesire~~		;cmmdc1out.txt
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:3		:3
	:15 9 6		:15 9 6

	== Exemplul 2 ==		== Exemplul 2 ==
	;~~Intrare~~		;cmmdc1in.txt
	:3 8		:3 8
	;7.2 8,0		;7.2 8,0
	~~;Iesire~~
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa: Pagină nouă: == Enunt == Fie un șir de numere naturale nenule a[1], a[2], …, a[n] și un număr natural k. == Cerinta == Să se determine un grup de k numere din șir care au proprietatea că cel mai mare divizor comun al lor este maxim. Dacă există mai multe astfel de grupuri, se cere acel grup pentru care suma elementelor este maximă. == Date de intrare == Fișierul de intrare cmmdc1.txt conține pe prima numerele naturale n k separate prin spațiu. Pe linia a doua se găsesc...

2023-12-15T14:36:27Z

Pagină nouă: == Enunt == Fie un șir de numere naturale nenule a[1], a[2], …, a[n] și un număr natural k. == Cerinta == Să se determine un grup de k numere din șir care au proprietatea că cel mai mare divizor comun al lor este maxim. Dacă există mai multe astfel de grupuri, se cere acel grup pentru care suma elementelor este maximă. == Date de intrare == Fișierul de intrare cmmdc1.txt conține pe prima numerele naturale n k separate prin spațiu. Pe linia a doua se găsesc...

New page

== Enunt ==

Fie un șir de numere naturale nenule a[1], a[2], …, a[n] și un număr natural k.

== Cerinta ==

Să se determine un grup de k numere din șir care au proprietatea că cel mai mare divizor comun al lor este maxim. Dacă există mai multe astfel de grupuri, se cere acel grup pentru care suma elementelor este maximă.

== Date de intrare ==

Fișierul de intrare cmmdc1.txt conține pe prima numerele naturale n k separate prin spațiu. Pe linia a doua se găsesc numerele naturale a[1], a[2], …, a[n] separate prin câte un spațiu.

== Date de iesire ==

Fișierul de ieșire cmmdc1.txt va conține pe prima linie un număr natural reprezentând cel mai mare divizor comun a exact k numere din șir, maxim posibil. Pe linia a doua, separate prin câte un spațiu și ordonate descrescător, se află cele k numere din șir care dau cel mai mare divizor comun maxim.

== Restrictii si precizari ==

*1 ≤ n ≤ 1.000.000
*2 ≤ k ≤ 100.000
*k ≤ n
*1 ≤ a[i] ≤ 1.000.000, i = 1..n
*Valorile din șir se pot repeta.

== Exemplul 1 ==
;Intrare
:6 3
:6 9 8 10 15 3
;Iesire
;Datele introduse corespund restrictiilor impuse
:3
:15 9 6

== Exemplul 2 ==
;Intrare
:3 8
;7.2 8,0
;Iesire
;Datele introduse nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from math import gcd

def cmmdc(a, b):
while b:
a, b = b, a % b
return a

def grup_cmmdc_maxim(n, k, numere):
grup_maxim = []
cmmdc_maxim = 0

for i in range(n - k + 1):
grup = numere[i:i+k]
cmmdc_grup = grup[0]
for numar in grup[1:]:
cmmdc_grup = cmmdc(cmmdc_grup, numar)

if cmmdc_grup > cmmdc_maxim:
cmmdc_maxim = cmmdc_grup
grup_maxim = grup

return cmmdc_maxim, grup_maxim

# Citire date de intrare
with open("cmmdc1.txt", "r") as file:
n, k = map(int, file.readline().split())
numere = list(map(int, file.readline().split()))

# Rezolvare problema
rezultat_cmmdc, rezultat_grup = grup_cmmdc_maxim(n, k, numere)

# Scriere rezultat în fișierul de ieșire
with open("cmmdc1.txt", "w") as file_out:
file_out.write(str(rezultat_cmmdc) + "\n")
file_out.write(" ".join(map(str, sorted(rezultat_grup, reverse=True))))

</syntaxhighlight>

== Explicatie ==

Cel mai mare divizor comun care se poate obține dintr-un grup de 3 numere este 3, iar cele 3 numere care dau suma maximă, ordonate descrescător, sunt 15 9 6.