Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Перестановки - 3

(Время: 1 сек. Память: 16 Мб Сложность: 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-перестановку в этом порядке.

Входные данные

Входной файл INPUT.TXT в первой строке содержит три натуральных числа – N (1 ≤ N ≤ 16), M и K (1 ≤ M, K ≤ 109). Вторая строка содержит N различных натуральных чисел, не превосходящих 109. Все числа в строках разделены пробелом.

Выходные данные

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

Примеры

INPUT.TXTOUTPUT.TXT
14 1 2
6 8 3 9
3 9 6 8
24 4 2
6 8 3 9
9 3 6 8
34 5 2
6 8 3 9
-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483