3415 - Vector Div

From Bitnami MediaWiki

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>