07/04/2025 05:57:30

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1200. Перестановки

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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/

29/01/2009	Областная олимпиада школьников по информатике. II тур. (8)
28/10/2015	Занятие по темам "Нумерация комбинаторных объектов, сокращение перебора" (D)