Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1200. Перестановки
Алгоритм ЭвклидаГенерация всех подмножеств, сочетаний, перестановок
Динамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 29/01/2009 | Областная олимпиада школьников по информатике. II тур. (8) |
| 28/10/2015 | Занятие по темам "Нумерация комбинаторных объектов, сокращение перебора" (D) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0) 
Задано множество из `n` различных натуральных чисел. Перестановку элементов этого множества назовем `k`-перестановкой, если для любых двух соседних элементов
этой перестановки их наибольший общий делитель не менее `k`. Например, если задано множество элементов `S\ =\ {6,\ 3,\ 9,\ 8}`, то перестановка `{8,\ 6,\ 3,\ 9}`
является 2-перестановкой, а перестановка `{6,\ 8,\ 3,\ 9}` – нет.
Перестановка `{p_1,\ p_2,\ …,\ p_n}` будет лексикографически меньше перестановки `{q_1,\ q_2,\ …,\ q_n}`, если существует
такое натуральное число `i` (`1\ ≤\ i\ ≤\ n`), для которого `p_j\ =\ q_j` при всех `j\ <\ i` и `p_i\ <\ q_i`.
В качестве примера упорядочим все `k`-перестановки заданного выше множества в лексикографическом порядке.
Например, существует ровно четыре 2-перестановки множества `S`: `{3,\ 9,\ 6,\ 8}`, `{8,\ 6,\ 3,\ 9}`, `{8,\ 6,\ 9,\ 3}` и `{9,\ 3,\ 6,\ 8}`.
Соответственно, первой 2-перестановкой в лексикографическом порядке является множество `{3,\ 9,\ 6,\ 8}`,
а четвертой – множество `{9,\ 3,\ 6,\ 8}`.
Требуется написать программу, позволяющую найти `m`-ую `k`-перестановку в этом порядке.
Формат входных данных
Входной файл в первой строке содержит три натуральных числа – `n` (`1 ≤ n ≤ 16`), `m` и `k` (`1 ≤ m, k ≤ 10^9`).
Вторая строка содержит `n` различных натуральных чисел, не превосходящих `10^9`. Все числа в строках разделены пробелом.
Формат выходных данных
В выходной файл необходимо вывести `m`-ую `k`-перестановку заданного множества или `-1`, если такой нет.
Примеры входных и выходных данных
input.txt
4 1 2 6 8 3 9
output.txt
3 9 6 8
input.txt
4 4 2 6 8 3 9
output.txt
9 3 6 8
input.txt
4 5 2 6 8 3 9
output.txt
-1
Примечание
Решения, работающие только для `n ≤ 10`, будут оцениваться из 50 баллов.
Источник: региональный этап Всероссийской олимпиады по информатике 2008/2009, http://neerc.ifmo.ru/school/