Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
-
глава 1. Динамическое программирование
(14 задач)
глава 2. Перебор с возвратом
(10 задач)
глава 3. Алгоритмы на графах
(17 задач)
глава 4. Вычислительная геометрия
(12 задач)
глава 5. Комбинаторные алгоритмы
(3 задачи)
глава 6. Задачи на разные темы
(12 задач)
Фильтр
Выбрана 1 задача Убрать все задачи
В стране 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
Решение
Задачи
Задача 102884[Четный граф ] |
|
|
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
|
|
Решение |
Задача 102890[Пиво в розлив] |
|
|
Изначально первая пробирка содержит 100 миллилитров пива, а остальные две пусты. Требуется написать программу, которая выясняет, можно ли отделить в третьей пробирке один миллилитр пива, и если да, то находит минимально необходимое для этого число переливаний. Пиво можно переливать из одной пробирки в другую до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какой-либо риски.
Входные данные
В первой строке входного файла содержится число рисок N (1 ≤ N ≤ 20),
имеющихся на каждой из первых двух пробирок. Затем в порядке возрастания
следуют N целых чисел V1
, ..., VN (1 ≤ Vi ≤ 100), приписанных рискам. Последняя
риска считается сделанной на верхнем крае пробирок
(VN
= 100).
Выходные данные
В первой строке выходного файла должна содержаться строка «YES», если в
третьей пробирке возможно отделить один миллилитр пива, и «NO» – в
противном случае. В случае ответа «YES» во вторую строку необходимо
вывести искомое количество переливаний.
Пример входного файла
4
13 37 71 100
Пример выходного файла
YES
8
|
|
|
Решение |
Задача 102893[Выгодней некуда ] |
|
|
Считается, что самолет может вместить не более одного груза, а временем
стоянки самолета в аэропорту следует пренебречь.
Входные данные
В первой строке входного файла содержится число городов 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
|
|
|
Решение |
Задача 102894[Считай путем ] |
|
|
Входные данные
Входной файл содержит количество вершин графа 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
|
|
|
Решение |
Задача 102895[Игра в города ] |
|
|
Входные данные
В первой строке входного файла записано целое число N – количество слов в списке (1 ≤ N ≤ 1000), а в последующих N строках – сами слова. Каждое из них является последовательностью не более чем из 10 строчных английских букв.
Выходные данные
Выведите в выходной файл слова в искомом порядке, либо сообщение «NO», если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.
Пример входного файла
4
b
ab
bc
bb
Пример выходного файла
ab
bb
b
bc
|
|
|
Решение |
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 67]
