Дано поле n × m. Есть кузнечик, который может прыгать вправо, вверх, по диагонали наверх не более чем на k клеток.

Необходимо за наименьшее кол-во прыжков передвинуть кузнечика с (1, 1) до (n, m).

Краткое решение: заметим что сначала выгодно прыгать по диагонали до упора в стенку. Затем прыгаем горизонтально или вертикально в зависмости от направления к финишу.

✗ Решение: https://codeforces.com/gym/105674/submission/314457151

Теги: [жадные алгоритмы, математика, реализация]

Дан массив a. Необходимо для каждого элемента посчитать сумму разностей этого элемента со строго меньшим и прибавить к ответу.

Краткое решение: посчитаем массив префиксных сумм pref. Тогда ответом для i-ого элемента будет a[i] * i - pref[i]. Это работает потому что наш ответ это фактически a[i] - a[i - 1] + a[i] - a[i - 2] + a[i] - a[i - 3] ... a[i] - a[1], что равно a[i] * i - pref[i - 1]. Заметим, что если у нас есть повторяющиеся значения, они будут уничтожены.

✓ Решение: https://codeforces.com/gym/106337/submission/383086795

Теги: [жадные алгоритмы]