Успішний інвестор#364

Успішний інвестор (Розбір)

Автор задачі:

Тимкович Олександр

Задачу підготував:

Тимкович Олександр

Розбір написав:

Тимкович Олександр

Будемо використовувати жадібний алгоритм. Ми знаємо, що повинно бути більшим за b_1, але немає ніяких нерівностей для b_1, то чому б нам b_1 не зробити мінімальним можливим, тобто a_1-x.

Припустимо, ми вже жадібно знайшли всі значення b_1,b_2,\dots,b_{i-1} і тепер потрібно знайти b_i. Будемо його заміняти на мінімальне можливе значення так, щоб всі умови досі виконувались.

У кінці, достатньо перевірити, чи b_1<b_2<\dots<b_n.