Автор задачі: | Тимкович Олександр |
Задачу підготував: | Тимкович Олександр |
Розбір написав: | Тимкович Олександр |
Будемо використовувати жадібний алгоритм. Ми знаємо, що повинно бути більшим за 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.