Advertisement
nq1s788

Untitled

Oct 20th, 2024
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.21 KB | None | 0 0
  1. Зафиксируем первый элемент (b[0]), выгоднее его не менять, а начать строить последовательность от него. Далее будем увеличивать каждый элемент b[i] на d, пока он не станет больше b[i - 1]. Заметим, что наше увеличение можно записать как неравенство b[i - 1] < b[i] + x * d, где x -- кол-во ходов. Преобразуем неравенство: b[i - 1] - b[i] < x * d <=> (b[i - 1] - b[i]) / d < x
  2.  
  3. x (кол-во ходов) должно быть минимальное целое, получается можем выразить его из нашего неравенства как x = (b[i - 1] - b[i]) // d, если b[i - 1] - b[i] не делится на d, и x = (b[i - 1] - b[i]) // d + 1, если b[i - 1] - b[i] делится на d.
  4.  
  5. Пример кода на python:
  6. n, d = map(int, input().split())
  7. b = list(map(int, input().split()))
  8. answ = 0
  9. for i in range(1, n):
  10.     if b[i] > b[i - 1]:
  11.         continue
  12.     x = (b[i - 1] - b[i]) // d
  13.     if (b[i - 1] - b[i]) % d == 0:
  14.         x += 1
  15.     answ += x
  16.     b[i] += d * x
  17. print(answ)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement