---> 8 задач <---
Источники
    Личные олимпиады(925 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Рассмотрим ориентированный граф G, имеющий n вершин, пронумерованных натуральными числами от 1 до n. В графе G возможно наличие нескольких дуг между одной и той же парой вершин, а также дуг, ведущих из вершины в нее саму. Каждая дуга графа помечена некоторой буквой латинского алфавита. Каждому пути в графе G можно поставить в соответствии строку, состоящую из букв, написанных на последовательно проходимых в соответствии с этим путем дугах. Эта строка называется путевой меткой пути. Назовем строку S путевой строкой графа G, если в нем существует путь, путевая метка которого равна S.

Ваша задача посчитать остаток от деления на 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, ≤ 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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
K-перестановкой чисел называется такая перестановка, в которой НОД соседних чисел не меньше K. Заданы числа из которых необходимо построить N-ую перестановку в лексикографическом порядке.

Задано множество из 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 ≤ mk ≤ 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
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

Стол имеет форму прямоугольника длиной 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
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено $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

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест