Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1712. Антиарифметическая последовательность
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 17/03/2012 | Южно-Уральский открытый командный чемпионат по программированию (A) |
| 24/03/2012 | Занятие 12 (A) |
| 19/07/2019 | Лето 2019 - 9 (командное) (G) |
Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Антиарифметическая последовательность формируется следующим образом:
`S_0=0`
`S_1=N`
`S_k` для всех `k>1` вычисляется как наименьшее целое число, такое что `S_k\ >\ S_{k-1}` и среди
элементов последовательности с номерами от 0 до `k` нет трех последовательных членов
арифметической прогрессии, т.е. не существует
`i,\ j` таких, что `0\ ≤\ i\ <\ j\ <\ k` и `S_k\ -\ S_j\ =\ S_j\ -\ S_i`.
Напишите программу, которая для заданного элемента последовательности `S_1=N` находит элементы
антиарифметической последовательности с номерами от `A` до `B`.
Формат ввода
Ввод содержит три целых числа `N` (`1\ ≤\ N\ ≤\ 1000`), `A` и `B` (`1\ ≤\ A\ <\ B\ ≤\ 3000`, `B-A\ <\ 100`).
Формат вывода
В первой строке вывести элементы антиарифметической последовательности с номерами от `A` до `B`, разделяя их пробелами.
Гарантируется, что величина элементов последовательности при заданных ограничениях не будет превышать `10^6`.
Пример ввода
2 1 10
Пример вывода
2 3 5 9 11 12 14 27 29 30
