Задан неориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая последовательно решает следующие задачи:
    а) выясняет количество компонент связности графа;
    б) находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;
    в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);
    г) ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;
    д) определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на пункт в) был утвердительным.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100) и список ребер графа, заданных номерами концевых вершин.

Выходные данные
Ваша программа должна вывести в выходной файл последовательно ответы на пункты a)-д) в следующем формате:
    в первой строке запишите ответ на пункт а);
    во второй строке запишите количество ребер из ответа на пункт б), а в последующих строках выдайте сами эти ребра;
    в следующую строку выведите сообщение «NOT POSSIBLE», если требуемым в пункте в) способом ориентировать граф невозможно, иначе выведите сообщение «POSSIBLE»;
    далее выведите максимальное количество ребер графа, которые можно ориентировать (пункт г); в последующие строки выведите список этих ребер;
    в качестве ответа на пункт д) выведите количество ребер, которые следует добавить в исходный граф, а далее выведите сами эти ребра.
Ребра задаются указанием номеров своих концевых вершин, а при выводе ответа на пункт г) должна быть указана их ориентация (вначале выводится номер начальной вершины, затем – номер конечной). Если ответ на пункт а) отличен от единицы, то пункты в) и г) решать не следует и ответы на них не выводятся. Баллы за пункт в) в случае утвердительного ответа на него начисляются лишь в том случае, если программа правильным образом ориентировала ребра графа (пункт г).

Пример входного файла
4
1 2
2 4
3 4
4 1

Пример выходного файла
1
1
3 4
NOT POSSIBLE
3
1 2
2 4
4 1
1
1 3

   Решение

Страница: << 3 4 5 6 7 8 9 >> [Всего задач: 67]      

Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v₁ и v₂ и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v₁ в вершину v₂, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v₁ в v₂ .

Входные данные
Первая строка входного файла содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во входном файле записаны без разделительных пробелов. 

Наконец, строка N+2 содержит номера вершин v₁ и v₂ , а строка N+3 – десятичную запись числа C (1 &le C < 10⁵⁰).

Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v₁ в v₂ не существует, ваша программа должна вывести -1.

Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555

Пример выходного файла
Yes
0

Прислать комментарий

Решение

Дано прямоугольное клетчатое поле M × N клеток. Каждая клетка поля покрашена в один из шести цветов, причем левая верхняя и правая нижняя клетки имеют различный цвет. В результате поле разбивается на некоторое количество одноцветных областей: две клетки одного цвета, имеющие общую сторону, принадлежат одной области.

Правила игры
Играют два игрока. За первым игроком закреплена область, включающая левую верхнюю клетку, за вторым – правую нижнюю. Игроки ходят по очереди. Делая ход, игрок перекрашивает свою область: 
    А) в любой из шести цветов;
    Б) в любой из шести цветов, за исключением цвета своей области и цвета области противника.
В результате хода к области игрока присоединяются все прилегающие к ней области выбранного цвета, если такие имеются. Если после очередного хода окажется, что области игроков соприкасаются, то игра заканчивается.

Задание
Напишите программу, которая для каждого из пунктов (А и Б) определяет минимально возможное число ходов, по прошествии которых игра может завершиться.

Входные данные
Цвета пронумерованы цифрами от 1 до 6. Первая строка входного файла содержит целые числа M и N – размеры поля (1 ≤ M,N ≤ 50). Далее следует описание раскраски поля – M строк по N цифр (от 1 до 6) в каждой без пробелов. Первая цифра файла соответствует цвету левой верхней клетки игрового поля. Количество одноцветных областей не превосходит 50.

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

Пример входного файла
4 3
122
221
143
132

Пример выходного файла
3
4

Прислать комментарий

Решение

Задан неориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая последовательно решает следующие задачи:
    а) выясняет количество компонент связности графа;
    б) находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;
    в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);
    г) ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;
    д) определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на пункт в) был утвердительным.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100) и список ребер графа, заданных номерами концевых вершин.

Выходные данные
Ваша программа должна вывести в выходной файл последовательно ответы на пункты a)-д) в следующем формате:
    в первой строке запишите ответ на пункт а);
    во второй строке запишите количество ребер из ответа на пункт б), а в последующих строках выдайте сами эти ребра;
    в следующую строку выведите сообщение «NOT POSSIBLE», если требуемым в пункте в) способом ориентировать граф невозможно, иначе выведите сообщение «POSSIBLE»;
    далее выведите максимальное количество ребер графа, которые можно ориентировать (пункт г); в последующие строки выведите список этих ребер;
    в качестве ответа на пункт д) выведите количество ребер, которые следует добавить в исходный граф, а далее выведите сами эти ребра.
Ребра задаются указанием номеров своих концевых вершин, а при выводе ответа на пункт г) должна быть указана их ориентация (вначале выводится номер начальной вершины, затем – номер конечной). Если ответ на пункт а) отличен от единицы, то пункты в) и г) решать не следует и ответы на них не выводятся. Баллы за пункт в) в случае утвердительного ответа на него начисляются лишь в том случае, если программа правильным образом ориентировала ребра графа (пункт г).

Пример входного файла
4
1 2
2 4
3 4
4 1

Пример выходного файла
1
1
3 4
NOT POSSIBLE
3
1 2
2 4
4 1
1
1 3

Прислать комментарий

Решение

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

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

Входные данные
Первая строка входного файла содержит целое число N – количество кратеров, отмеченных на карте (1 ≤ N ≤ 500). Следующие N строк содержат описания кратеров с номерами от 1 до N. Описание каждого кратера занимает отдельную строку и состоит из трех целых чисел, принадлежащих диапазону [-32768, 32767] и разделенных пробелами. Первые два числа представляют собой декартовы координаты его центра, а третье – радиус. Все кратеры различны.

Выходные данные
Первая строка выходного файла должна содержать длину искомой цепочки кратеров, вторая – номера кратеров из этой цепочки, начиная с меньшего кратера и кончая самым большим. Номера кратеров должны быть разделены пробелами. Если существует несколько длиннейших цепочек, следует вывести любую из них.

Пример входного файла
4
0 0 30
-15 15 20
15 10 5
10 10 10

Пример выходного файла
3
3 4 1

Прислать комментарий

Решение

Имеется таблица M × N, в каждой ячейке которой записано либо целое число, либо арифметическая формула. В формулах могут присутствовать целые числа, знаки *, /, +, -, (, ), пробелы и ссылки на значения из других ячеек таблицы, записываемые в виде {НомерCтроки, НомерCтолбца} (например, {1,10}). Требуется вычислить значения во всех ячейках заданной таблицы.

Входные данные:
В первой строке входного файла записаны целые числа M и N (1 ≤ M, N ≤ 20). В каждой из последующих M строк содержится описание очередной строки таблицы. Описание состоит из целых чисел и арифметических формул, разделенных символами | (ASCII-код 124). Все числа принадлежат диапазону [-32768, 32767], а длина каждой формулы не превышает 100 символов.

Выходные данные:
Выведите в выходной файл значения всех ячеек таблицы. Значения ячеек каждой строки таблицы должны быть записаны через пробел в отдельной строке выходного файла. Все значения следует выводить с точностью до двух знаков после десятичной точки. Если значение ячейки вычислить невозможно, вместо него следует вывести символ - (ASCII-код 45).

Пример входного файла
2  3
  1      |    {1, 1   }*10        +3 |     -{1,2}/{2,2}
{2,3} |             0                     |           {2,1}

Пример выходного файла
1.00 13.00 -
- 0.00 -

Прислать комментарий

Решение

Страница: << 3 4 5 6 7 8 9 >> [Всего задач: 67]