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

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

Перестановка {p₁, p₂, …, p_n} будет лексикографически меньше перестановки {q₁, q₂, …, 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⁹). Вторая строка содержит n различных натуральных чисел, не превосходящих 10⁹. Все числа в строках разделены пробелом.

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

Примеры

Театр

Олег и Сергей − мастера по свету в одном из театров. В их задачу входит управление подсветкой сцены во время спектакля. Спектакль состоит из действий, во время каждого из которых некоторые лампы подсветки должны быть включены, а некоторые выключены. В перерывах между действиями занавес закрывается, и Олег с Сергеем должны включить на сцене набор ламп, необходимый для следующего действия.

Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.

Театральная сцена представляет собой прямоугольник W на L метров, внутри которого расположено N ламп подсветки.

Кулисы состоят из двух не связанных между собой частей − левой и правой. Левая часть кулис целиком прилегает к левой стороне сцены, а правая − целиком к правой.

Олег может перемещаться по сцене с максимальной скоростью V₁ метров в секунду, а Сергей − V₂ метров в секунду. Мастера могут находиться на сцене только в перерывах между действиями. Во время действия они могут переместиться в любую точку в пределах той части кулис, в которой они оказались перед началом действия.

Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий M и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей − в правой. Изначально включены лампы, необходимые для первого действия.

Задача Олега и Сергея − организовать работу так, чтобы суммарное время всех перерывов между действиями было бы минимальным.

Входные данные
На первой строке входного файла находится пять чисел − W,L,V₁,V₂ и N (1≤W,L≤50, 1≤V₁,V₂≤20, 1 ≤ N ≤ 15)− размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно.

Далее идут N строк с координатами ламп подсветки в метрах x_i,y_i (0<x_i<L, 0<y_i<W).

Следующая строка содержит число M(1≤M≤10000) − число действий в спектакле. Далее идут M строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.

Выходные данные
В выходной файл выведите единственное число − минимальное суммарное время перерывов между действиями в секундах с точностью 10^-5.

Cow Decathlon

Problem 2: Cow Decathlon [Lewin Gan]
N коров Фермера Джона (1 <= N <= 20), последовательно пронумерованных от 1 до 20 готовятся к десятиборью, в котором имеется N различных событий (из чего следует, что его правильнее было называть N-борьем, в отличие десятиборья, в котором традиционно ровно 10 событий).
Корова I имеет уровень мастерства S_ij (1 <= s_ij <= 1000), когда соревнуется в событии j. Каждая корова должна соревноваться в одном и только одном событии и каждом событии должна участвовать некоторая корова.
Общий счёт для всех коров - это сумма их уровней мастерства для тех соревнований, в которых они соревнуются. Однако жюри может также добавить бонусные баллы, если оно особенно впечатлено.
Всего имеется B бонусов (1<=B<=20), которые может дать жюри. Бонус I описывается 3 числами: - если коровы получат не менее чем P_i баллов(1 <= P_i <= 40,000) за первые K_i событий (включая другие бонусы, полученные на этих событиях), то они получат дополнительные A_i баллов (1 <= A_i <= 1000).
Например, рассмотрим N=3 коров со следующими уровнями мастерства:
E V E N T | 1 | 2 | 3 --+---+---+-- C 1 | 5 | 1 | 7 --+---+---+-- O 2 | 2 | 2 | 4 --+---+---+-- W 3 | 4 | 2 | 1
Например, корова 1 заработает 7 баллов команде, если она поучаствует в событии 3.
Предположим, что судьи дадут один бонус (B=1), такой что если коровы заработают не менее 7 баллов в первых двух событиях, то они получат дополнительные 6 баллов. Следовательно, оптимально будет назначить корову 1 событию 1, корову 2 событию 3 и корову 3 событию 2. За первые два события корова 1 получит 5 баллов и корова 3 получит 2 балла, что в сумме даст 7 и удовлетворяет бонусу 1. Поэтому, общее количество заработанных баллов будет 5+2+4+6=17.
Помогите распределиться коровам по событиям так, чтобы максимизировать их общий счёт.
PROBLEM NAME: dec
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа: N, B
* Строки 2..B+1: Строка i+1 содержит информацию о бонусе i задаваемом тремя разделёнными пробелами целыми числами: K_i, P_i, A_i.
* Строки B+2..B+N+1: Строки B+1+j содержат информацию о том, как корова i выполняет каждое из событий, с помощью N разделённых пробелами целых чисел: s_j1...s_jN.