Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2148. Ахроматическое число графа
Эйлеров путь/циклОлимпиадные задачи на русском языке
| 22/07/2014 | Лето 2014 - 16 (командное) (I) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Хроматическим числом графа называют минимальное количество цветов, которое
необходимо для того, чтобы раскрасить его вершины таким образом, чтобы
никакие две вершины одного цвета не были соединены ребром.
Такая раскраска вершин графа называется правильной.
Известно, что нахождение хроматического числа графа является трудной задачей.
Правильная раскраска графа в свою очередь называется ахроматической,
если каждая пара различных цветов встречается на концах некоторого ребра.
Ахроматическим числом графа называют максимальное количество цветов,
которое можно использовать для раскраски вершин графа, чтобы полученная
раскраска была ахроматической.
Например, ахроматическое число треугольника равно трем, поскольку если раскрасить
все его вершины в различные цвета, каждая пара цветов будет встречаться на концах
некоторого ребра.
Вам дано число `n`. Найдите ахроматическое число цикла длиной `n`
и выведите соответствующую ахроматическую раскраску.
Входной файл содержит одно целое число `n` (`3\ ≤\ n\ ≤\ 1000`).
На первой строке выходного файла выведите одно число `a` – ахроматическое
число цикла длиной `n`. Вторая строка должна содержать `n` целых чисел в диапазоне
от 1 до `a` и описывать соответствующую правильную ахроматическую раскраску.
Пример ввода
3
Пример вывода
3 1 2 3
