| | | |
|
Гном
Динамика по подмножествам
Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено N точек, в которых может находиться клад. Все точки пронумерованы числами от 1 до N. Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером 1. Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером 1 никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.
Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.
Входные данные
В первой строке находится одно целое число N (1 ≤ N ≤ 15) — количество точек, отмеченных на карте. В последующих N строках находятся расстояния между точками. В (i+1)-й строке находятся N целых чисел di1,di2, diN — длины дорог от i-й точки до всех остальных. Гарантируется, что dij=dji, dii=0 и 0 <dij <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 различных натуральных чисел. Перестановку элементов этого множества назовем 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 ≤ m, k ≤ 109). Вторая строка содержит n различных натуральных чисел, не превосходящих 109. Все числа в строках разделены пробелом.
Выходные данные
В выходной файл необходимо вывести 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 |
| |
![]()
|
|
Счастливый билетик
Динамика по подмножествам
В стране Лаккиландии очень развит общественный транспорт. Проезд в нем бесплатный, но при этом каждому пассажиру при входе выдают билетик с уникальным номером. Особенно ценятся так называемые счастливые билетики.
Билетик называется счастливым, если сумма цифр на четных позициях в его номере равна сумме цифр на нечетных позициях.
Ване известно, что билеты выдаются подряд в порядке возрастания номеров. В очередной раз войдя в автобус Ваня получил свой очередной билет и тут ему стало интересно, какой существует минимальный счастливый билетик с номером, большим номера Ваниного билетика. Помогите Ване узнать ответ на этот вопрос.
Входные данные
В единственной строке входного файла задан номер Ваниного билетика − натуральное число, имеющее в своей десятичной записи не более 100 цифр.
Выходные данные
В выходной файл выведите минимальный номер счастливого билетика, который больше номера Ваниного билетика.
| |
![]()
|
|
Театр
Динамика по подмножествам
Олег и Сергей − мастера по свету в одном из театров. В их задачу входит управление подсветкой сцены во время спектакля. Спектакль состоит из действий, во время каждого из которых некоторые лампы подсветки должны быть включены, а некоторые выключены. В перерывах между действиями занавес закрывается, и Олег с Сергеем должны включить на сцене набор ламп, необходимый для следующего действия.
Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.
Театральная сцена представляет собой прямоугольник W на L метров, внутри которого расположено N ламп подсветки.
Кулисы состоят из двух не связанных между собой частей − левой и правой. Левая часть кулис целиком прилегает к левой стороне сцены, а правая − целиком к правой.
Олег может перемещаться по сцене с максимальной скоростью V1 метров в секунду, а Сергей − V2 метров в секунду. Мастера могут находиться на сцене только в перерывах между действиями. Во время действия они могут переместиться в любую точку в пределах той части кулис, в которой они оказались перед началом действия.
Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий M и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей − в правой. Изначально включены лампы, необходимые для первого действия.
Задача Олега и Сергея − организовать работу так, чтобы суммарное время всех перерывов между действиями было бы минимальным.
Входные данные
На первой строке входного файла находится пять чисел − W,L,V1,V2 и N (1≤W,L≤50, 1≤V1,V2≤20, 1 ≤ N ≤ 15)− размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно.
Далее идут N строк с координатами ламп подсветки в метрах xi,yi (0<xi<L, 0<yi<W).
Следующая строка содержит число M(1≤M≤10000) − число действий в спектакле. Далее идут M строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.
Выходные данные
В выходной файл выведите единственное число − минимальное суммарное время перерывов между действиями в секундах с точностью 10-5.
| |
![]()
|
