Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача H регионального тура. Перестановки

Автор задачи: Региональный этап Всероссийской олимпиады школьников по информатике 2008 / 2009 учебного года

Задачу добавил: alef

Успешно сдано решений: 9

Время на тест - 2 с
Максимальный объем используемой памяти - 64 Мб

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p1, p2, …, pn} будет лексикографически меньше перестановки {q1, q2, …, qn}, если существует такое натуральное число i (1 ≤ i n), для которого pj = qj при j < i и pi < qi.

В качестве примера упорядочим все 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 ≤ mk ≤ 109). Вторая строка содержит n различных натуральных чисел, не превосходящих 109. Все числа в строках разделены пробелом.

Формат выходных данных

В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

Примеры входных и выходных данных

perm.in

perm.out

4 1 2

6 8 3 9

3 9 6 8

4 4 2

6 8 3 9

9 3 6 8

4 5 2

6 8 3 9

-1

Примечание

Решения, работающие только для n  10, будут оцениваться из 50 баллов.

 


Сдать задачу

Задать вопрос жюри по этой задаче