3415 - Vector Div: Diferență între versiuni
De la Universitas MediaWiki
Mraa (discuție | contribuții) (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...) |
Mraa (discuție | contribuții) Fără descriere a modificării |
||
Linia 22: | Linia 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 | |||
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) | print(result) | ||
</syntaxhighlight> |
Versiunea curentă din 11 ianuarie 2024 18:16
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)