3415 - Vector Div: Difference between revisions
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... |
No edit summary |
||
| 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 | |||
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> | |||
Latest revision as of 18:16, 11 January 2024
Cerința[edit | edit source]
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[edit | edit source]
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.
Date de ieșire[edit | edit source]
Programul va afișa pe ecran numărul minim de operații.
Restricții și precizări[edit | edit source]
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[edit | edit source]
Un exemplu de vector care respectă condiția este 1 5 5 10.
Rezolvare[edit | edit source]
<syntaxhighlight lang="python3" line="1"> 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) </syntaxhighlight>