Динамика по подмножествам

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

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

Театральная сцена представляет собой прямоугольник 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.

Дана таблица \(A\) из \(h\) строк и \(w\) столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от \(1\) до \(h\) сверху вниз, столбцы пронумерованы от \(1\) до \(w\) слева направо.

Разрешается применять к этой таблице следующие операции:

• выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);

• выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу \(s\), и если да, то какие операции и в каком порядке необходимо применить.

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

Первая строка ввода содержит числа \(h\) и \(w\) — размеры таблицы (\(1 \leq h, w \leq 15\)).

Каждая из следующих \(h\) строк содержит по \(w\) целых чисел — таблицу \(A\) (\(0 \leq A_{i,j} \leq 10^{9}\)).

В последней строке ввода находится число \(s\) — необходимая сумма (\(1 \leq s \leq 10^{18}\)).

Формат выходных данных
Если получить таблицу с суммой чисел \(s\) из исходной невозможно, выведите строку <<NO>>.

Иначе:

• В первой строке выведите строку <<YES>>.

• Во второй строке выведите единственное число \(k\) — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел \(s\).

• В каждой из следующих \(k\) строк выведите по два целых числа \(t_{j}, i_{j}\), где \(t_{j} = 1\), если очередная операция производится со строкой, и \(t_{j}=2\), если она производится со столбцом таблицы. Число \(i_{j}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

В первом примере изначально дана следующая таблица:

Удалив третьи строку и столбец получим таблицу с суммой чисел \(8\):

Во втором примере можно показать, что разрешенными операциями невозможно получить таблицу с суммой чисел \(5\) из исходной.

В третьем примере изначально дана таблица:

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел \(34\):

Задано множество из 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, если такой нет.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 6 8 3 9	3 9 6 8
2	4 4 2 6 8 3 9	9 3 6 8
3	4 5 2 6 8 3 9	-1

Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено N точек, в которых может находиться клад. Все точки пронумерованы числами от 1 до N. Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером 1. Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером 1 никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.

Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.

Входные данные
В первой строке находится одно целое число N (1 ≤ N ≤ 15) — количество точек, отмеченных на карте. В последующих N строках находятся расстояния между точками. В (i+1)-й строке находятся N целых чисел d_i1,d_i2, d_iN — длины дорог от i-й точки до всех остальных. Гарантируется, что d_ij=d_ji, d_ii=0 и 0 <d_ij <100. В (N+2)-й строке находится одно целое число Q (1 < Q ≤ 1000) — количество вариантов вычеркивания точек для данной карты. В последующих Q строках содержится описание вариантов вычеркивания. Описание начинается с числа C (0 ≤ C < N) — количества точек, в которых, по мнению Кварка, клада быть не может. Следующие C чисел задают номера этих точек.

Выходные данные
Выведите Q строк. В каждой строке выведите одно целое число — длину минимального маршрута при соответствующем варианте вычеркивания точек.

Примеры

№	Входные данные	Выходные данные
1	3 0  45 10 45 0  30 10 30 0 2 0 1 3	40 45
2	5 0  14 20 17 14 14 0  15 19 18 20 15 0  15 16 17 19 15 0  14 14 18 16 14 0 2 3 5 4 3 0	14 58

Дочь короля Флатландии собирается выйти за прекрасного принца. 
Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать.

В коллекции принца n бриллиантов, каждый характеризуется весом w_i и стоимостью v_i. 
Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L.

Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L, R].

Входные данные:
Первая строка содержит число n (1 <= n <= 32), L и R (0 <= L <= R <= 10¹⁸).
Следующие n строк описывают бриллианты и содержат по два числа - вес и стоимость соответствующего бриллианта (1 <= wi, vi <= 10¹⁵).

Выходные данные:
Первая строка вывода должна содержать k - количество бриллиантов, которые нужно подарить принцессе. 
Вторая строка должна содержать номера даримых бриллиантов.
Бриллианты нумеруются от 1 до n в порядке появление во входных данных.

Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода.

Примеры:
 

Входные данные	Выходные данные
3 6 8 3 10 7 3 8 2	1 2

Казума путешествует с тремя спутницами: Аквой, Мегумин и Даркнесс. Но за путешествия не платят, поэтому нашему отряду необходимо выполнять задания, порученные гильдией авантюристов.

Казума уже выбрал n заданий, которые необходимо выполнить. Однако всегда, когда отряд в полном сборе берется за что-то, то происходят непредвиденные и абсурдные вещи. Именно поэтому Казума решил, что на каждое из заданий он возьмет ровно двух спутниц.

Отношение каждой из спутниц к Казуме характеризуется целым числом. Изначально отношение каждой из них нейтрально и равно 0. В процессе выполнения задания отношение девушек, которых он взял на задание, к нему меняется в положительную или отрицательную сторону (а может и не меняться вовсе).

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

Помогите Казуме определить, какое наибольшее, равное для всех девушек, отношение к нему он может получить.

Входные данные:
В первой строке содержится целое положительное число n (1 ≤ n ≤ 25) — количество заданий, обязательных для выполнения.
Следующие n строк содержат описание заданий — i-я строка содержит три числа a_i, m_i, d_i — величины, на которые изменятся отношения к Казуме Аквы, Мегумин или Даркнесс соответственно, в случае, если герой возьмет их с собой на выполнение i-го задания. 
Все числа во входных данных целые и не превышают по абсолютному значению 10⁷.

Выходные данные:
В случае, если решения не существует, в первой строке выведите "Impossible".
В противном случае выведите отношение, которое будет у всех девушек по отношению к Казуме и при этом максимально возможное.

Примеры:
 

Входные данные	Выходные данные
3 1 0 0 0 1 0 0 0 1	1
7 0 8 9 5 9 -2 6 -8 -7 9 4 5 -4 -9 9 -4 5 2 -6 8 -7	5
2 1 0 0 1 1 0	Impossible

Задано прямоугольное поле размера n*m. В каждой клетке записано целое неотрицательное число. Требуется посчитать количество путей из клетки (1,1) в клетку (n,m), удовлетворяющих следующим условиям.
1) Из каждой клетки можно перемещаться только вниз или вправо, не выходя при этом за пределы поля.
2) Побитовое исключающее ИЛИ всех чисел на пути должно быть равно k.
Найдите количество подходящих путей для заданного поля.

Входные данные
Первая строка содержит три целых числа n, m и k (1 <= n, m <= 20, 0 <= k <= 10¹⁸) - высота и ширина поля, и число k.
Следующие n строк содержат по m целых чисел ai,j, где j-й элемент i-й строки равен ai,j (0 <= a_i,j <= 10¹⁸).

Выходные данные
Выведите одно целое число - количество путей, удовлетворяющих всем условиям.
 

Примеры

№	Входные данные	Выходные данные
1	3 3 11 2 1 5 7 10 0 12 6 4	3
2	3 4 2 1 3 3 3 0 3 3 2 3 0 1 1	5

Дан массив A, состоящий из n целых положительных чисел, и число m. Выберите последовательность позиций B1, B2, ..., Bk (1 <= B₁ < B₂ < ... < B_k <= n) такую, чтобы значение  \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) было максимально (то есть, чтобы остаток от деления суммы элементов подпоследовательности на число m был максимально возможным). Выбранная последовательность может быть пустой.
Посчитайте максимальное возможно значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\).

Входные данные
В первой строке даны два целых числа n и m (1 <= n <= 35, 1 <= m <= 10⁹). Во второй строке дано n целых чисел A1, A2, ..., An (1 <= A_i <= 10⁹)

Выходные данные
Выведите одно число - максимальное значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

 

Примеры

№	Входные данные	Выходные данные
1	4 4 5 2 4 1	3
2	3 20 199 41 299	19

 

Пояснения

В первом примере можно выбрать B = {1, 2}. (A1 + A2) mod m = (5 + 2) % 4 = 3.
Во втором примере можно выбрать B = {3}.