Задача A. Отрезки с наложением ≡
| Автор: | Г. Гренкин | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt |
Условие
Дано N отрезков с длинами w1, …, wN. Требуется расположить их на интервале числовой оси [0, L] так, чтобы они покрыли этот интервал без пропусков и не выходили за его границы.
Необходимо использовать все отрезки. Отрезки можно накладывать друг на друга.
Формат входного файла
Первая строка входного файла содержит целые числа N и L.
Вторая строка содержит N целых чисел w1 w2… wN.
Формат выходного файла
Выходной файл должен содержать N целых чисел x1 x2… xN — координаты левых концов отрезков.
Если решения не существует, то выходной файл должен содержать единственное число − 1. Если существует несколько решений, вывести любое из них.
Ограничения
1 ≤ N ≤ 1000, 1 ≤ L ≤ 10000, 1 ≤ wi ≤ 10000.
Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
Разбор
Если сумма всех wi меньше L или максимальное wi больше L, то покрыть отрезок длиной L невозможно.
Иначе координаты левых концов отрезков можно выбрать, например, так:
