Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1853. Monotonic Subsequence
Задачи на построениеОлимпиадные задачи на английском языке
| 25/04/2003 | 7-й Чемпионат Урала. 2 тур (2) |
| 08/07/2013 | Лето 2013-5 (B) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Let us consider some permutation of numbers from 1 to 10, for example (10, 1, 8, 3, 4, 7, 5, 6, 2, 9). The longest
increasing subsequence is (1, 3, 4, 5, 6, 9). Its length equals 6. The longest decreasing subsequence
is (10, 8, 7, 5, 2). Its length equals 5. So, the length of the most long monotonic (increasing or decreasing)
subsequence equals 6.
Your program must find permutation of numbers from 1 to `N` with minimal length of the longest monotonic subsequence,
where `N` is a given integer number.
Input
The first line of the input file contains single integer `N` (`1\ ≤\ N\ ≤\ 1000`).
Output
Write into the first line of the output file the number, which is equal to minimal length of
the longest monotonic subsequence of permutation of numbers from 1 to `N`. The second line of the output file
should contain such permutation `(a_1,\ a_2,\ …,\ a_N)` with mentioned property, that gives the minimal
value of expression `a_1*N^{N–1}+a_2*N^{N–2}+…+a_{N–1}*N+a_N`, i.e. the first permutation in lexicographic order with mentioned property.
The elements of permutation would be separated by one space.
Sample Input
9
Sample Output
3 3 2 1 6 5 4 9 8 7
