Mraa at 18:16, 11 January 2024

2024-01-11T18:16:44Z

← Older revision		Revision as of 18:16, 11 January 2024
Line 22:		Line 22:
	Un exemplu de vector care respectă condiția este 1 5 5 10.		Un exemplu de vector care respectă condiția este 1 5 5 10.
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3" line="1">
	def min_operations(n, values):		def min_operations(n, values):
	~~max_value = max(values)~~
	~~dp = [[float('inf')] * (max_value + 1) for _ in range(n)]~~

	# Inițializăm prima coloană a matricei dp		max_value = max(values)
	for j in range(1, max_value + 1):		dp = [[float('inf')] * (max_value + 1) for _ in range(n)]
	dp[0][j] = min(abs(values[0] - j), j - 1)		# Inițializăm prima coloană a matricei dp
			for j in range(1, max_value + 1):
			dp[0][j] = min(abs(values[0] - j), j - 1)
			for i in range(1, n):
			for j in range(1, max_value + 1):
			for k in range(1, max_value + 1):
			if j % k == 0:
			dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(values[i] - j))
			# Alegem minimul din ultima linie a matricei dp
			result = min(dp[n - 1])
			return result
			Citim input-ul

	~~for i in range~~(~~1, n):~~		n = int(input()) values = list(map(int, input().split()))
	~~for j in range~~(~~1, max_value + 1~~):
	~~for k in range(1, max_value + 1~~):
	~~if j % k~~ =~~= 0:~~
	~~dp[i][j] = min~~(~~dp[i][j]~~, ~~dp[i - 1][k] + abs~~(~~values[i] - j~~))

	~~# Alegem minimul din ultima linie a matricei dp~~		Calculăm rezultatul
	~~result = min(dp[n - 1])~~

	~~return~~ result		result = min_operations(n, values)

	~~# Citim input-ul~~		Afișăm rezultatul
	~~n = int(input())~~
	~~values = list(map(int, input().split()))~~

	~~# Calculăm~~ rezultatul
	~~result = min_operations(n, values)~~

	~~# Afișăm rezultatul~~
	print(result)		print(result)
			</syntaxhighlight>

Mraa: Pagină nouă: ==Cerința== Se da un vector cu n elemente. Asupra fiecărui element putem efectua 2 tipuri de operații: să-l adunăm sau să-l scădem cu 1. La final, fiecare element trebuie să fie divizor al elementului următor. Adică, v[i] îl divide pe v[i + 1], oricare ar fi 1 ≤ i < n. Știind că ultimul element nu poate fi modificat, aflați numărul minim de operații pentru ca vectorul să îndeplinească condiția dată. ==Date de intrare== Programul citește de la tastatur...

2023-12-25T13:36:17Z

Pagină nouă: ==Cerința== Se da un vector cu n elemente. Asupra fiecărui element putem efectua 2 tipuri de operații: să-l adunăm sau să-l scădem cu 1. La final, fiecare element trebuie să fie divizor al elementului următor. Adică, v[i] îl divide pe v[i + 1], oricare ar fi 1 ≤ i < n. Știind că ultimul element nu poate fi modificat, aflați numărul minim de operații pentru ca vectorul să îndeplinească condiția dată. ==Date de intrare== Programul citește de la tastatur...

New page

==Cerința==
Se da un vector cu n elemente. Asupra fiecărui element putem efectua 2 tipuri de operații: să-l adunăm sau să-l scădem cu 1. La final, fiecare element trebuie să fie divizor al elementului următor. Adică, v[i] îl divide pe v[i + 1], oricare ar fi 1 ≤ i < n. Știind că ultimul element nu poate fi modificat, aflați numărul minim de operații pentru ca vectorul să îndeplinească condiția dată.

==Date de intrare==
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

==Date de ieșire==
Programul va afișa pe ecran numărul minim de operații.

==Restricții și precizări==
1 ≤ n ≤ 10
cele n numere citite vor fi mai mici sau egale cu 1.000.000
==Exemplu==:
Intrare

4
2 8 4 10
Ieșire

5
==Explicație==
Un exemplu de vector care respectă condiția este 1 5 5 10.
==Rezolvare==
def min_operations(n, values):
max_value = max(values)
dp = [[float('inf')] * (max_value + 1) for _ in range(n)]

# Inițializăm prima coloană a matricei dp
for j in range(1, max_value + 1):
dp[0][j] = min(abs(values[0] - j), j - 1)

for i in range(1, n):
for j in range(1, max_value + 1):
for k in range(1, max_value + 1):
if j % k == 0:
dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(values[i] - j))

# Alegem minimul din ultima linie a matricei dp
result = min(dp[n - 1])

return result

# Citim input-ul
n = int(input())
values = list(map(int, input().split()))

# Calculăm rezultatul
result = min_operations(n, values)

# Afișăm rezultatul
print(result)

3415 - Vector Div - Revision history

Mraa at 18:16, 11 January 2024