Страница:
<< 1 2
3 4 5 6 7 >> [Всего задач: 67]
[Четный граф
]
|
|
Сложность: 3 |
Неориентированный граф называется четно-нечетным, если найдутся две его
вершины, между которыми существует пути как из четного, так и из нечетного
числа ребер. Напишите программу, которая:
a) определяет, является ли заданный граф четно-нечетным;
б) В случае отрицательного ответа на пункт
а) находит максимальное подмножество X вершин графа такое, что для любых двух вершин i и j из X
выполняется следующее условие: все пути между i и j состоят из четного числа
ребер.
Входные данные
Первая строка входного файла содержит число вершин графа N
(1 ≤ N ≤ 100), а каждая последующая – пару чисел (i, j), означающих, что в графе присутствует
ребро, соединяющее вершины с номерами i и j.
Выходные данные
Первая строка выходного файла должна содержать ответ на пункт А в форме
YES/NO. В случае отрицательного ответа на пункт А вторая строка должна
содержать количество вершин в множестве X, а третья – номера вершин из
этого множества в порядке возрастания, записанные через пробел. Если
вариантов решений несколько, то достаточно вывести любое из них.
Пример входного файла
3
1 2
Пример выходного файла
NO
2
2 3
[Пиво в розлив]
|
|
Сложность: 3 |
Имеются три пробирки, вместимостью 100 миллилитров каждая. Первые две
пробирки имеют риски, одинаковые на обеих пробирках. Возле каждой риски
надписано целое число миллилитров, которое вмещается в часть пробирки от
дна до этой риски (см. рисунок).
Изначально первая пробирка содержит 100 миллилитров пива, а остальные
две пусты. Требуется написать программу, которая выясняет, можно ли
отделить в третьей пробирке один миллилитр пива, и если да, то находит
минимально необходимое для этого число переливаний. Пиво можно
переливать из одной пробирки в другую до тех пор, пока либо первая из них не
станет пустой, либо одна из пробирок не окажется заполненной до какой-либо
риски.
![](show_document.php?id=1424224)
Входные данные
В первой строке входного файла содержится число рисок N (1 ≤ N ≤ 20),
имеющихся на каждой из первых двух пробирок. Затем в порядке возрастания
следуют N целых чисел V1
, ..., VN (1 ≤ Vi ≤ 100), приписанных рискам. Последняя
риска считается сделанной на верхнем крае пробирок
(VN
= 100).
Выходные данные
В первой строке выходного файла должна содержаться строка «YES», если в
третьей пробирке возможно отделить один миллилитр пива, и «NO» – в
противном случае. В случае ответа «YES» во вторую строку необходимо
вывести искомое количество переливаний.
Пример входного файла
4
13 37 71 100
Пример выходного файла
YES
8
[Выгодней некуда
]
|
|
Сложность: 3 |
В стране N городов, в каждом из которых есть аэропорт. Авиакомпания,
занимающаяся перевозкой грузов, имеет самолет и желает максимально
выгодно его использовать. Для некоторых пар городов (A, B) известны время
перелета из A в B и сумма выручки за доставку груза из A в
B. Напишите программу, которая по этим данным находит для самолета замкнутый путь,
максимизирующий среднюю выручку за единицу времени.
Считается, что самолет может вместить не более одного груза, а временем
стоянки самолета в аэропорту следует пренебречь.
Входные данные
В первой строке входного файла содержится число городов N
(1 ≤ N ≤ 100) и число возможных прямых рейсов M. В каждой из следующих M строк записана
четверка чисел (i, j, bij, cij), описывающая возможный рейс между городами i и j
со временем перелета bij
и выручкой cij
. Время перелета и выручка – положительные вещественные числа.
Выходные данные
В первой строке выходного файла должна содержаться максимальная средняя
выручка за единицу времени, а во второй – замкнутый маршрут, заданный
номерами своих вершин в порядке следования, на котором эта максимальная
выручка достигается. Первая и последняя вершины маршрута должны
совпадать. Входные данные будут таковы, что решение заведомо будет
существовать.
Пример входного файла
3 3
1 2 1.0 2.0
2 3 1.0 2.0
3 1 2.0 1.0
Пример выходного файла
1.25
1 2 3 1
[Считай путем
]
|
|
Сложность: 3 |
Задан ориентированный граф с N вершинами, пронумерованными целыми
числами от 1 до N. Напишите программу, которая подсчитывает количество
различных путей между всеми парами вершин графа.
Входные данные
Входной файл содержит количество вершин графа N (1 ≤
N ≤ 33) и список дуг графа, заданных номерами начальной и конечной вершин.
Выходные данные
Вывести в выходной файл матрицу N × N, элемент (i, j) которой равен числу
различных путей, ведущих из вершины i в вершину j, или -1, если существует
бесконечно много таких путей.
Пример входного файла
5
1 2
2 4
3 4
4 1
5 3
1 1
Пример выходного файла
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 1 -1 0
[Игра в города
]
|
|
Сложность: 3 |
Всем известны правила игры «в города»: первый игрок называет произвольный
город, следующий – город, название которого начинается на ту же букву, на
которую заканчивается название предыдущего города, и т.д. Аналогичным
образом можно играть не в названия городов, а, например, в названия
животных.
Задан список допустимых для описанной игры слов, слова в нем могут
повторяться. Напишите программу, определяющую, в каком порядке в процессе
игры должны быть названы слова из списка, чтобы каждое слово было
использовано ровно столько раз, сколько оно в нем встречается.
Входные данные
В первой строке входного файла записано целое число N – количество слов в
списке (1 ≤ N ≤ 1000), а в последующих N строках – сами слова. Каждое из них
является последовательностью не более чем из 10 строчных английских букв.
Выходные данные
Выведите в выходной файл слова в искомом порядке, либо сообщение «NO»,
если такого порядка не существует. Каждое слово должно быть выведено в
отдельную строку выходного файла.
Пример входного файла
4
b
ab
bc
bb
Пример выходного файла
ab
bb
b
bc
Страница:
<< 1 2
3 4 5 6 7 >> [Всего задач: 67]