ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2015

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Различные суммы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Алексей — серьёзный математик, и он любит решать серьёзные задачи. Вот, например, одна из этих задач.
Необходимо построить массив из целых чисел длины n, в котором не менее k различных чисел, такой, что количество различных сумм на подотрезках минимально. Другими словами, необходимо рассмотреть все подотрезки массива, посчитать на каждом сумму чисел и убрать повторяющиеся суммы. Количество оставшихся сумм и нужно минимизировать.

Исходные данные

В единственной строке даны целые числа n, k (1 ≤ kn ≤ 500) через пробел.

Результат

В единственной строке выведите n целых чисел, разделённых пробелом — ответ на задачу. Все числа должны быть не больше 106 по модулю. Гарантируется, что существует оптимальное решение, в котором все числа не более 105 по модулю. Если есть несколько оптимальных ответов, выведите любой из них.

Примеры

исходные данныерезультат
1 1
-987654
3 2
0 7 0

Замечания

Рассмотрим второй тестовый пример и обозначим сумму чисел на отрезке с l по r как sum(l, r) (индексация начинается с 1). Тогда sum(1, 1) = sum(3, 3) = 0, sum(1, 2) = sum(1, 3) = sum(2, 2) = sum(2, 3) = 7, то есть количество различных сумм равно 2.
Автор задачи: Никита Сивухин (подготовка — Алексей Данилюк, Никита Сивухин)
Источник задачи: Уральская региональная командная олимпиада по программированию 2015
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2065. Различные суммы