Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Зафиксируем первый элемент (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
- 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.
- Пример кода на python:
- n, d = map(int, input().split())
- b = list(map(int, input().split()))
- answ = 0
- for i in range(1, n):
- if b[i] > b[i - 1]:
- continue
- x = (b[i - 1] - b[i]) // d
- if (b[i - 1] - b[i]) % d == 0:
- x += 1
- answ += x
- b[i] += d * x
- print(answ)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement