Задача №113582. Водянистая гистограмма Мирко
Ночью Мирко приснилась гистограмма из N столбиков. Каждый из них имел ширину в 1 метр, а высоты столбиков в метрах равны h 1 , h 2 , ... , h N .
Вместимостью гистограммы называется максимальное количество воды (в квадратных метрах) которое она может удержать так, что конфигурация воды "стабильная", иными словами, вода в ней не перемещается под воздействием сил гравитации.
Формально, пусть количество воды над столбиками равно v 1 , v 2 , ... , v N соответственно. Тогда конфигурация воды стабильна, если выполняются следующие условия:
1. h i + v i ≤ h i - 1 + v i - 1 для каждого i ≥ 2 , такого что v i > 0 .
2. h i + v i ≤ h i + 1 + v i + 1 для каждого i ≤ N - 1 , такого что v i > 0 .
3. v 1 = 0 и v N = 0 .
Проснувшись, Мирко захотел нарисовать такую гистограмму, чтобы высоты ее столбиков были перестановкой множества {1, 2, ... , N} и ее вместимость была в точности равна его счастливому числу X . Помогите Мирко и найдите такую гистограмму.
Единственная строка содержит два целых числа N и X ( 1 ≤ N ≤ 1000000 , 1 ≤ X ≤ 10 15 ).
Если гистограмма вместимости X не существует, выведите -1.
Иначе, выведите числа h 1 , h 2 , ... , h N (являющиеся перестановкой множества {1, 2, ... , N}), удовлетворяющие условию задачи. Если существует несколько решений, выведите любое.
25 баллов — (1 ≤ n ≤ 10) .
25 баллов — (0 ≤ x ≤ n - 2 ) .
50 баллов — полные ограничения.
3 1
3 1 2
4 1
4 3 1 2
8 17
6 2 3 1 8 4 5 7