Рассмотрим ориентированный граф G, имеющий n вершин, пронумерованных натуральными числами от 1 до n. В графе G возможно наличие нескольких дуг между одной и той же парой вершин, а также дуг, ведущих из вершины в нее саму. Каждая дуга графа помечена некоторой буквой латинского алфавита. Каждому пути в графе G можно поставить в соответствии строку, состоящую из букв, написанных на последовательно проходимых в соответствии с этим путем дугах. Эта строка называется путевой меткой пути. Назовем строку
Ваша задача посчитать остаток от деления на 1 000 000 количества путевых строк графа G, состоящих ровно из L символов.
В первой строке входных данных записаны целые числа n, m, L (1 ≤ n ≤ 10, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 100), равные количеству вершин и ребер графа G, а также длине путевых строк, которые нужно искать. Следующие m строк задают дуги графа G. Каждая из этих строк содержит два натуральных числа a, b (1 ≤ a, b ≤ n) и маленькую латинскую букву c, что означает наличие дуги из вершины a в вершину b, помеченной символом c. Элементы каждой строки отделены друг от друга пробелами.
Единственная строка выходных данных должна содержать одно число, равное остатку от деления количества путевых строк длины L в графе G на 1 000 000.
4 4 100 1 2 a 2 3 b 3 4 a 4 1 b
2
Олег и Сергей \(-\) мастера по свету в одном из театров. В их задачу входит управление подсветкой сцены во время спектакля. Спектакль состоит из действий, во время каждого из которых некоторые лампы подсветки должны быть включены, а некоторые выключены. В перерывах между действиями занавес закрывается, и Олег с Сергеем должны включить на сцене набор ламп, необходимый для следующего действия.
Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.
Театральная сцена представляет собой прямоугольник \(W\) на \(L\) метров, внутри которого расположено \(N\) ламп подсветки.
Кулисы состоят из двух не связанных между собой частей \(-\) левой и правой. Левая часть кулис целиком прилегает к левой стороне сцены, а правая \(-\) целиком к правой.
Олег может перемещаться по сцене с максимальной скоростью \(V_1\) метров в секунду, а Сергей \(-\) \(V_2\) метров в секунду. Мастера могут находиться на сцене только в перерывах между действиями. Во время действия они могут переместиться в любую точку в пределах той части кулис, в которой они оказались перед началом действия.
Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий \(M\) и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей \(-\) в правой. Изначально включены лампы, необходимые для первого действия.
Задача Олега и Сергея \(-\) организовать работу так, чтобы суммарное время всех перерывов между действиями было бы минимальным.
На первой строке входного файла находится пять чисел \(-\) \(W, L, V_1, V_2\) и \(N\) (\(1 \le W, L \le 50\), \(1 \le V_1, V_2 \le 20\), \(1 \le N \le 15\))\(-\) размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно.
Далее идут \(N\) строк с координатами ламп подсветки в метрах \(x_i, y_i\) (\(0 < x_i < L\), \(0 < y_i < W\)).
Следующая строка содержит число \(M\)(\(1 \le M \le 10\,000\)) \(-\) число действий в спектакле. Далее идут \(M\) строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.
В выходной файл выведите единственное число \(-\) минимальное суммарное время перерывов между действиями в секундах с точностью \(10^{-5}\).
5 6 1 1 3 1 2 3 4 5 3 1 1 3
0.000000000000000
5 6 1 1 3 1 2 3 4 5 3 3 1 3 2 1 2 3 1 2 3
8.828427124746190
Задано множество из 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-3 — из условия. Оцениваются в 0 баллов.
Тесты 4-17 — \(n\le 4\). Группа тестов оценивается в 28 баллов.
Тесты 18-28 — \(n\le 10\). Группа тестов оценивается в 22 балла (вместе с предыдущей группой — 50 баллов).
Тесты 29-53 — дополнительных ограничений нет. Группа тестов оценивается в 50 баллов (вместе с предыдущими группами — 100 баллов).
Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп. При выставлении баллов за отдельные тесты каждый тест (кроме тестов из условия) оценивается в 2 балла.
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
Роботы начинают все чаще использоваться в домашнем хозяйстве. Один программист решил сделать робота для своих хозяйственных нужд. Как известно, многие программисты потребляют напиток "Живчик", от которого на столе остаются разбросанные пустые бутылки. Поэтому он решил запрограммировать робота собирать пустые бутылки со стола.
Стол имеет форму прямоугольника длиной l и шириной w. Робот стартует в точке xr, yr, а N бутылок расположены в точках xi, yi (для i от 1 до N).
Чтобы убрать бутылку робот должен дойти до нее, взять ее, донести до любого края стола и сбросить. Робот может держать только одну бутылку, поэтому убирает он их по очереди.
Размером робота и бутылок можно пренебречь, в том числе можно считать что робот свободно может пройти мимо любой бутылки. Напишите программу, которая определяет минимальную длину пути робота, который ему необходимо пройти, чтобы убрать все бутылки со стола.
Первая строка входного файла содержит два целых числа w и l. (2 ≤ w, l ≤ 1000). Вторая строка входных данных содержит N – число бутылок на столе (1 ≤ N ≤ 18). Каждая из следующих N строк содержит два целых числа xi, yi – координаты i-й бутылки на столе (0<xi<w; 0<yi<l). Никакие две бутылки не находятся в одной точке.
Последняя строка входного файла содержит 2 целых числа xr, yr – координаты начальной позиции робота (опять же не у края стола и не в точке с бутылкой).
Выведите длину кратчайшего пути робота с точностью не менее 6 значащих цифр после точки.
3 4 2 1 1 2 3 2 1
5.60555127546399
Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено \(N\) точек, в которых может находиться клад. Все точки пронумерованы числами от \(1\) до \(N\). Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером \(1\). Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером \(1\) никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.
Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.
В первой строке находится одно целое число \(N\) \((1 \lt N \le 15)\) — количество точек, отмеченных на карте. В последующих \(N\) строках находятся расстояния между точками. В \((i + 1)\)-й строке находятся \(N\) целых чисел \(d_{i1},\, d_{i2},\, \ldots,\, d_{iN}\) — длины дорог от \(i\)-й точки до всех остальных. Гарантируется, что \(d_{ij} = d_{ji}\), \(d_{ii} = 0\) и \(0 \lt d_{ij} \lt 100\). В \((N + 2)\)-й строке находится одно целое число \(Q\) \((1 \lt Q \le 1000)\) — количество вариантов вычеркивания точек для данной карты. В последующих \(Q\) строках содержится описание вариантов вычеркивания. Описание начинается с числа \(C\) \((0 \le C \lt N)\) — количества точек, в которых, по мнению Кварка, клада быть не может. Следующие \(C\) чисел задают номера этих точек.
Выведите \(Q\) строк. В каждой строке выведите одно целое число — длину минимального маршрута при соответствующем варианте вычеркивания точек.
3 0 45 10 45 0 30 10 30 0 2 0 1 3
40 45
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