Вывод в файл OUTPUT. TXT. В единственной строке вывести с точностью до 2 знаков минимальное время в месяцах с момента высадки, необходимое для того, чтобы в результате слияния осталось не более K поселений.
Ограничения. Время работы на одном тесте до 2 с. Объем используемой памяти: 64 мегабайта.
Пример
Ввод
3 2 1
-1 1
2 1
2 5
Вывод
1.50
12.7. Шпионские страсти (9)
Резидент разведки руководит сетью секретных агентов, контактируя только с некоторыми из них. Каждый агент имеет право передавать информацию определенному кругу других агентов. Множество тех партнеров, которым агент передает сведения, не обязано совпадать с множеством принимающих от него информацию агентов. Полученные данные могут распространяться далее и, в конечном счете, доставляются резиденту. Резидент оплачивает каждую передачу сведений от одного агента другому. Величина оплаты зависит от пары агентов и от того, кто из них принимает информацию. Таким образом, общая оплата доставки информации зависит только от цепочки агентов, участвующих в доставке, и действующих расценок.
Стало известно, что определенный агент добыл ценные секретные сведения. В целях надежности резидент решил получить информацию по двум независимым каналам, то есть через разных агентов. Требуется найти минимальный размер затрат резидента для оплаты передачи информации по двум цепочкам агентов, которые начинаются с удачливого агента и заканчиваются резидентом, не пересекаясь друг с другом.
Ввод из файла INPUT. TXT. Первая строка содержит три целых положительных числа N, A и B, разделённых пробелом: N – количество агентов, включая резидента, A – номер начального агента, а B – номер конечного агента, то есть резидента. Далее следуют N строк, описывающих связи агентов в виде матрицы стоимости Cij. В i-й строке задаются через пробел стоимости передачи информации от агента с номером i агентам с номерами 1, 2, …, N соответственно в виде целых положительных чисел, то есть значения Ci1, Ci2,…, CiN. Бесплатной передачи информации между агентами не существует. Если i-й агент не связан с j-м, то в соответствующем месте ставится 0. Связи каждого агента с самим собой заполняются нулями, то есть главная диагональ матрицы стоимостей состоит из нулей.
Ограничения: N ≤ 50, 0 ≤ Cij ≤ 10000, время 2 с.
Вывод в файл OUTPUT. TXT. В единственной строке выводится минимальная суммарная стоимость передачи информации по двум непересекающимся цепочкам агентов. Если таких цепочек не находится, в файл OUTPUT. TXT выводится строка со словом No.
Примеры
Ввод 1 Ввод 2
4 1 4 4 1 3
0 2 3 9 0 5 2 0
1 0 0 6 2 0 4 7
1 2 0 5 0 1 0 0
0 0 0 0 3 7 0 0
Вывод 1 Вывод 2
16 No
12.8. Учебный план (6)
Учебный план включает перечень дисциплин. Задан список пар дисциплин. Отдельная пара показывает, что вторая дисциплина должна изучаться после первой. Составить список дисциплин учебного плана в порядке их изучения. В том случае, когда задание некорректно, т. е. в списке пар имеются циклы, выдать хотя бы один из них.
Ввод из файла INPUT. TXT. В первой строке задается число пар дисциплин N (1 ≤ N ≤ 300). В каждой из следующих N строк указываются через пробел два натуральных числа Xi , Yi (Xi , Yi ≤ 1000), определяющих номера дисциплин. Первая дисциплина должна изучаться раньше второй.
Вывод в файл OUTPUT. TXT. В первой строке вывести Yes либо No – возможность расположения в списке дисциплин в порядке их изучения. При наличии такой возможности во второй строке выводится через пробел искомый список. Если задание некорректно, т. е. имеется цикл, то во второй строке выдается список номеров, образующих цикл. Первый и последний номера в этом списке должны совпадать.
Примеры
Ввод 1 Ввод 2
7 8
1 2 1 2
1 3 1 3
2 5 2 5
3 4 3 4
4 2 4 2
3 2 3 2
6 4 6 4
5 3
Вывод 1 Вывод 2
Yes No
1 6 3 4 2 5 2 5 3 4 2
12.9. Морские дьяволы (6)
Полигон для тренировки морских десантников представляет собой площадку в форме прямоугольника с водоемами и задается матрицей размером M x N. Каждый элемент матрицы содержит либо символ '@', обозначающий участок водной поверхности, либо символ '.' (точка), обозначающий участок суши. Подразделение морских дьяволов находится в клетке, соответствующей левому верхнему углу матрицы. Ему поставлена задача достичь участка, соответствующего правому нижнему углу матрицы. Десантники могут передвигаться в направлениях вдоль сторон полигона, не выходя за его пределы. Они планируют преодолеть как можно меньше клеток, занятых водой. Если это можно сделать по-разному, то предпочтительнее такой вариант, когда путь включает меньшее количество клеток суши.
Ввод из файла INPUT. TXT. В первой строке содержатся числа M и N (1 £ M, N £ 50), разделенные пробелами. В следующих M строках находится матрица, представляющая полигон, по N подряд идущих символов в строке. Гарантируется, что левый верхний и правый нижний углы матрицы соответствуют участкам суши.
Вывод в файл OUTPUT. TXT. В единственной строке вывести через пробел наименьшее число клеток K, которое подразделение должно преодолеть по воде, и для найденного значения K минимальное число клеток по суше L, включая начальную и конечную клетки.
Примеры
Ввод 1 Ввод 2
7 7 7 6
..@@... .@@@..
..@@@.. ......
@.@@..@ @.@@.@
@@@...@ @@@..@
*****@***..@...
..@...@ ..@...
*****@***....@.
Вывод 1 Вывод 2
1 14 0 12
12.10. Детали (7)
Некоторое предприятие выпускает двигатели для автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия заключается в том, что одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей. Генеральный директор поставил перед предприятием задачу: за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке. Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдет наименьшее время, за которое можно произвести деталь с номером 1.
Ввод из файла INPUT. TXT. Первая строка содержит число n (1 ≤ n ≤ 100000) – количество деталей двигателя. Вторая строка содержит n натуральных чисел p1, p2 … pn , определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 109 секунд. Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. Сумма всех чисел ki не превосходит 200000. Известно, что не существует циклических зависимостей в производстве деталей.
Вывод в файл OUTPUT. TXT. В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел – номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.
Примеры
Ввод 1 Ввод 2 Ввод 3
3 2 4
100 200 300 2 3 2 3 4 5
1 2 1 2 2 3 2
0 0 1 3
2 2 1 0
2 1 3
Вывод 1 Вывод 2 Вывод 3
300 2 5 2 9 3
2 1 2 1 3 2 1
12.11. Слабая K-связность (6)
Ане, как будущей чемпионке мира по программированию, поручили очень ответственное задание. Правительство вручает ей план постройки дорог между N городами. По плану все дороги односторонние, но между двумя городами может быть больше одной дороги, возможно, в разных направлениях. Ане необходимо вычислить такое минимальное K, что данный ей план является слабо K-связным.
Правительство называет план слабо K-связным, если выполнено следующее условие: для любых двух различных городов можно проехать от одного до другого, нарушая правила движения не более K раз. Нарушение правил – это проезд по дороге в обратном направлении. Гарантируется, что между любыми двумя городами можно проехать, возможно, несколько раз нарушив правила.
Ввод. В первой строке записаны два числа N и M (2 ≤ N ≤ 300; 1 ≤ M ≤ 105)– количество городов и дорог в плане. В следующих M строках содержатся по два числа – номера городов, в которых начинается и заканчивается соответствующая дорога.
Вывод. Выведите минимальное K, такое, что данный во входном файле план является слабо K-связным.
Примеры
Ввод 1 Ввод 2
3 2 4 4
1 2 2 4
1 3 1 3
4 1
3 2
Вывод 1 Вывод 2
1 0
12.12. Олимпиада (7)
На олимпиаде по программированию предложено N задач. Требуется решить как можно больше задач. Если два участника решили одинаковое количество задач, то впереди оказывается тот, который имеет меньшее суммарное штрафное время. Это время определяется как сумма по всем зачтенным задачам времен их сдачи в минутах. Если, например, участник сдал 3 задачи на 10-й, 45-й и 123-й минутах, то штрафное время будет равно 10 + 45 +123 =178 минут.
Один из участников точно определил время, необходимое для решения каждой задачи. Кроме того он выявил, что решение части задач потребуется для сдачи других более сложных задач, поэтому эти простые задачи должны быть решены раньше. Каждое такое условие задается упорядоченной парой (a, b), которая определяет, что задача a должна быть решена раньше задачи b (если обе они будут решены). В этом случае ta ≤ tb, где ta и tb – необходимые затраты времени для решения задач a и b. Участник решает задачи последовательно, приступая к следующей после полного завершения предыдущей. Выведите наибольшее количество задач, которое сможет решить участник за время T, суммарное штрафное время при их решении и номера задач в порядке их решения.
Ввод. В первой строке входного файла содержатся два натуральных числа N и T (1 ≤ N ≤ 200; 1 ≤ T ≤ 106). Во второй строке записаны N чисел ti (1 ≤ ti ≤ 1000), где ti – время решения i-й задачи. В третьей строке записано число M (0 ≤ M ≤ 1000) – количество условий. Далее вводится M строк, каждая из которых содержит условие в виде двух целых чисел ai и bi (1 ≤ ai, bi ≤ N; ai ≠bi), которое обозначает, что задача ai должна решаться раньше задачи bi. Гарантируется, что время решения задачи ai не больше времени решения задачи bi. Все числа во входном файле целые.
Вывод. В первой строке выходного файла выведите два целых числа A и B, где A – наибольшее количество задач, а B – минимальное штрафное время. Во второй строке должны содержаться номера задач в порядке их решения. Если вариантов несколько, выведите любой из них.
Примеры
Ввод 1 Ввод 2 Ввод 3
1 1 3 10 4 2
1 1 1 1 1 2 1 2
0 3 1
1 2 1 3
2 3
3 1
Вывод 1 Вывод 2 Вывод 3
1 1 0 0 2 3
1 1 3
12.13. Контрабандисты (10)
В некоторой местности имеется сеть автомобильных дорог. Каждая дорога соединяет два разных населенных пункта. Пункты пронумерованы от 1 до N. Известно, какой максимальный груз можно провезти по каждой из дорог. Движение по дорогам возможно в обоих направлениях.
Контрабандисты мечтают доставить как можно больше своего нелегального товара из пункта A в пункт B. Им стало известно, что полиция готовит засаду для конфискации товара. Засада может быть организована на какой-либо дороге или в некотором населенном пункте, исключая пункты A и B. Контрабандисты решили отправить товар двумя партиями по двум разным путям, которые не имеют общих населенных пунктов и дорог. Какой наибольший груз можно гарантированно доставить из пункта A в пункт B?
Ввод. В первой строке содержатся через пробел значения N, M, A и B, где N – количество населенных пунктов (3 ≤ N ≤ 30), M – число дорог, A и B – номера начального и конечного населенных пунктов (A ≠ B). В каждой из следующих M строк находятся через пробел три значения Ui, Vi, Hi, задающие параметры очередной дороги. Значения Ui и Vi (1 ≤ Ui < Vi ≤ 30) определяют номера населенных пунктов на концах дороги, а Hi (1 ≤ Hi ≤ 105) указывает максимальный груз, который можно провезти по этой дороге. Все значения целые и положительные.
Вывод. Единственная строка должна содержать величину наибольшего гарантированного груза, который можно доставить из пункта A в пункт B с учетом пропускной способности дорог и возможности перехвата полицией одной из партий. Если двух различных путей из пункта A в пункт B не существует, вывести в выходной файл No.
Пример
Ввод 1 Ввод 2 Ввод 3
3 3 3 1 4 2 3 4 3 2 1 2
1 3 5 1 2 5 1 2 5
1 2 7 1 3 3 1 3 3
3 2 4
Вывод 1 Вывод 2 Вывод 3
4 No No
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
