|
ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
|
Подтемы:
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
Страница: << 1 2 3 4 5 6 [Всего задач: 28]
Изначально у Пети имеется один грамм свинца. С помощью философского камня Петя может превратить свой свинец в другие вещества, на которые он потом также сможет воздействовать философским камнем. Выполняя одну за другой алхимические реакции, Петя стремится получить как можно больше золота. Требуется написать программу, определяющую по заданному описанию
алхимических реакций, выполняемых философским камнем, наибольшее
количество золота, которое может получить Петя.
В третьей строке записано целое число L – количество типов реакций,
выполняемых философским камнем (1 ≤ L ≤ 100). Далее идут L описаний этих
реакций. Каждое описание реакции состоит из двух строк: первая строка
содержит название вещества, которое подвергается превращению, вторая –
названия веществ, получающихся в результате реакции.
1) определить, существует ли в заданном графе путь из вершины v1 в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам); 2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v1 в v2 . Входные данные Первая строка входного файла содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во входном файле записаны без разделительных пробелов.
Наконец, строка N+2 содержит номера вершин v1
и v2
, а строка N+3 – десятичную запись числа C (1 &le C <
1050).
Страница: << 1 2 3 4 5 6 [Всего задач: 28] |
|
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
|