Тема:
Информатика
-
Знакомство с языком программирования
(107 задач)
Алгоритмы
(155 задач)
Математика
(39 задач)
Информатика (прочее)
(3 задачи)
Фильтр
Задачи
Задача 102788[Взлом сети ] |
|
|
КГБ хочет прослушивать все передаваемые в сети Пентагона сообщения.
Для этого советскими программистами был разработан вирус, который, будучи
установлен на какой-либо из компьютеров, передает КГБ всю информацию,
проходящую через него. Оказалось, что материальные затраты, необходимые
для установки вируса на различные компьютеры, различны. Требуется
определить набор компьютеров, которые КГБ должно инфицировать, чтобы
минимизировать общие материальные затраты.
Входные данные
Первая строка входного файла содержит N – количество компьютеров в сети
(1 ≤ N ≤ 500). В i-й из последующих N строк содержатся номера компьютеров,
с которыми непосредственно связан компьютер номер i. Далее следуют N целых
чисел из диапазона [1, 1000] – материальные затраты, связанные с установкой
вируса на каждый из компьютеров.
Выходные данные
В выходной файл выведите минимально возможные суммарные затраты и
список номеров компьютеров, которые нужно инфицировать, упорядоченный
по возрастанию.
Пример входного файла
5
5
4
4
2 3 5
4 1
1 5 5 2 10
Пример выходного файла
3
1 4
|
|
Решение |
Задача 102790[Длинный путь в графе ] |
|
|
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).
Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи:
«Yes», если путь длины C существует, и «No», если нет. Во вторую строку
запишите ответ на второй пункт задачи. Если ни одного пути из v1
в v2
не существует, ваша программа должна вывести -1.
Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555
Пример выходного файла
Yes
0
|
|
|
Решение |
Задача 102791[Навстречу друг другу ] |
|
|
Правила игры
Играют два игрока. За первым игроком закреплена область, включающая левую верхнюю клетку, за вторым – правую нижнюю. Игроки ходят по очереди. Делая ход, игрок перекрашивает свою область:
А) в любой из шести цветов;
Б) в любой из шести цветов, за исключением цвета своей области и цвета области противника.
В результате хода к области игрока присоединяются все прилегающие к ней области выбранного цвета, если такие имеются. Если после очередного хода окажется, что области игроков соприкасаются, то игра заканчивается.
Задание
Напишите программу, которая для каждого из пунктов (А и Б) определяет минимально возможное число ходов, по прошествии которых игра может завершиться.
Входные данные
Цвета пронумерованы цифрами от 1 до 6. Первая строка входного файла содержит целые числа M и N – размеры поля (1 ≤ M,N ≤ 50). Далее следует описание раскраски поля – M строк по N цифр (от 1 до 6) в каждой без пробелов. Первая цифра файла соответствует цвету левой верхней клетки игрового поля. Количество одноцветных областей не превосходит 50.
Выходные данные
В выходной файл выведите искомое количество ходов для каждого из пунктов. Если ваша программа решает только один из пунктов, выведите произвольное целое число в качестве ответа на другой пункт.
Пример входного файла
4 3
122
221
143
132
Пример выходного файла
3
4
|
|
|
Решение |
Задача 102885[Ориентация графа ] |
|
|
а) выясняет количество компонент связности графа;
б) находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;
в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);
г) ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;
д) определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на пункт в) был утвердительным.
Входные данные
Во входном файле записано целое число 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
|
|
|
Решение |
Задача 102886[Кратеры на Луне ] |
|
|
Увлекающийся астрономией профессор З. В. Ездочетов занялся изучением
современной карты участка лунной поверхности. Он решил найти на ней
максимально длинную цепочку вложенных друг в друга кратеров. Зная о Ваших
недюжинных способностях в области построения алгоритмов, за помощью в
решении этой непростой задачи он обратился к Вам.
Входные данные
Первая строка входного файла содержит целое число 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
|
|
|
Решение |
Страница: << 29 30 31 32 33 34 35 >> [Всего задач: 277]
